On the parameterized complexity of short computation and factorization
Academic Article
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
A completeness theory for parameterized computational complexity has been studied in a series of recent papers, and has been shown to have many applications in diverse problem domains including familiar graph-theoretic problems VLSI layout, games, computational biology, cryptography, and computational learning [ADF,BDHW,BFH, DEF,DF1-7,FHW,FK]. We here study the parameterized complexity of two kinds of problems: (1) problems concerning parameterized computations of Turing machines, such as determining whether a nondeterministic machine can reach an accept state in k steps (the SHORT TM COMPUTATION PROBLEM), and (2) problems concerning derivations and factorizations, such as determining whether a word x can be derived in a grammar G in k steps, or whether a permutation has a factorization of length k over a given set of generators. We show hardness and completeness for these problems for various levels of the W hierarchy. In particular, we show that SHORT TM COMPUTATION is complete for W [1]. This gives a new and useful characterization of the most important of the apparently intractable parameterized complexity classes.
