Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues (Q1892937)

The paper devices some new results in parametrized complexity theory. In particular, it is proved that a number of concrete hardness results for W[P], the top level of the hardness hierarchy introduced by Downey and Fellows in a series of earlier papers. This hierarchy for fixed-parameter problems is based on the logical depth needed to describe the respective problem in terms of circuits. Furthermore, analogs of PSPACE are studied in the fixed-parameter setting. This is done via certain problems concerning \(k\)-move games. Several aspects of the structural complexity of W[P] and related classes are studied. The class W[P] is characterized in terms of DTIME \((2^{o(n)})\) and NP.