1,720,977 research outputs found
Perfect Code is W[1]-complete
No full textWe show that the parameterized problem Perfect Code belongs to W[1]. This result closes an old open question, because it was often conjectured that Perfect Code could be a natural problem having complexity degree intermediate between W[1] and W[2]. This result also shows W[1]-membership of the parameterized problem Weighted Exact CNF Satisfiability. © 2002 Elsevier Science B.V. All rights reserved
On the efficiency of polynomial time approximation schemes
No full textA polynomial time approximation scheme (PTAS) for an optimization problem A is an algorithm that given in input an instance of A and ε > 0 finds a (1 + ε)-approximate solution in time that is polynomial for each fixed ε. Typical running times are nO(1/ε) or 21/εO(1) n. While algorithms of the former kind tend to be impractical, the latter ones are more interesting. In several cases, the development of algorithms of the second type required considerably new, and sometimes harder, techniques. For some interesting problems, only nO(1/ε) approximation schemes are known. Under likely assumptions, we prove that for some problems (including natural ones) there cannot be approximation schemes running in time f(1/ε)nO(1), no matter how fast function f grows. Our result relies on a connection with Parameterized Complexity Theory, and we show that this connection is necessary
Computation models for parameterized complexity
Full text linkA parameterized computational problem is a set of pairs 〈x, k〉, where k is a distinguished item called "parameter". FPT is the class of fixed-parameter tractable problems: for any fixed value of k, they are solvable in time bounded by a polynomial of degree α, where a is a constant not dependent on the parameter. In order to deal with parameterized intractability, Downey and Fellows have introduced a hierarchy of classes W[I] ⊆ W[2] ⊆ ⋯ containing likely intractable parameterized problems, and they have shown that such classes have many natural, complete languages. In this paper we analyze several variations of the halting problem for nondeterministic Turing machines with parameterized time, and we show that its parameterized complexity strongly depends on some resources like the number of tapes, head and internal states, and on the size of the alphabet. Notice that classical polynomial-time complexity fails in distinguishing such features. As byproducts, we show that parameterized complexity is a useful tool for the study of the intrinsic power of some computational models, and we underline the different "computational powers" of some levels of the parameterized hierarchy
The Turing way to parameterized complexity
Full text linkAbstractWe propose a general proof technique based on the Turing machine halting problem that allows us to establish membership results for the classes W[1], W[2], and W[P]. Using this technique, we prove that Perfect Code belongs to W[1], Steiner Tree belongs to W[2], and α-Balanced Separator, Maximal Irredundant Set, and Bounded DFA Intersection belong to W[P]
Parameterized parallel complexity
No full textWe introduce a framework to study the parallel complexity of parameterized problems, and we propose some analogs of NC
Understanding the Linux kernel, Third Edition
No full textThe book describes the most significant data structures, algorithms, and programming ticks used in the Linux kernel
Sparse parameterized problems
No full textSparse languages play an important role in classical structural complexity theory. In this paper we introduce a natural definition of sparse problems for parameterized complexity theory. We prove an analog of Mahaney's theorem: there is no sparse parameterized problem which is hard for the tth level of the W hierarchy, unless the W hierarchy itself collapses up to level t. The main result is proved for the most general form of parametric many:1 reducibility, where the parameter functions are not assumed to be recursive. This provides one of the few instances in parameterized complexity theory of a full analog of a major classical theorem. The proof involves not only the standard technique of left sets, but also substantial circuit combinatorics to deal with the problem of small weft, and a diagonalization to cope with potentially nonrecursive parameter functions. The latter techniques are potentially of interest for further explorations of parameterized complexity analogs of classical structural results
Parameterized Complexity Analysis in Robot Motion Planning
No full textthis paper, using the theory of parameter
- …
