ﻻ يوجد ملخص باللغة العربية
The central conjecture of parameterized complexity states that FPT is not equal to W[1], and is generally regarded as the parameterized counterpart to P != NP. We revisit the issue of the plausibility of FPT != W[1], focusing on two aspects: the difficulty of proving the conjecture (assuming it holds), and how the relation between the two classes might differ from the one between P and NP. Regarding the first aspect, we give new evidence that separating FPT from W[1] would be considerably harder than doing the same for P and NP. Our main result regarding the relation between FPT and W[1] states that the closure of W[1] under relativization with FPT-oracles is precisely the class W[P], implying that either FPT is not low for W[1], or the W-Hierarchy collapses. This theorem also has consequences for the A-Hierarchy (a parameterized version of the Polynomial Hierarchy), namely that unless W[P] is a subset of some level A[t], there are structural differences between the A-Hierarchy and the Polynomial Hierarchy. We also prove that under the unlikely assumption that W[P] collapses to W[1] in a specific way, the collapse of any two consecutive levels of the A-Hierarchy implies the collapse of the entire hierarchy to a finite level; this extends a result of Chen, Flum, and Grohe (2005). Finally, we give weak (oracle-based) evidence that the inclusion of W[t] in A[t] is strict for t>1, and that the W-Hierarchy is proper. The latter result answers a question of Downey and Fellows (1993).
Computation plays a key role in predicting and analyzing natural phenomena. There are two fundamental barriers to our ability to computationally understand the long-term behavior of a dynamical system that describes a natural process. The first one i
In this work, we show the first worst-case to average-case reduction for the classical $k$-SUM problem. A $k$-SUM instance is a collection of $m$ integers, and the goal of the $k$-SUM problem is to find a subset of $k$ elements that sums to $0$. In t
We consider the complexity properties of modern puzzle games, Hexiom, Cut the Rope and Back to Bed. The complexity of games plays an important role in the type of experience they provide to players. Back to Bed is shown to be PSPACE-Hard and the firs
This document presents a simpler proof showcasing the NP-hardness of Familial Graph Compression.
We study the problem of approximating the value of a Unique Game instance in the streaming model. A simple count of the number of constraints divided by $p$, the alphabet size of the Unique Game, gives a trivial $p$-approximation that can be computed