Ka. Abrahamson et al., FIXED-PARAMETER TRACTABILITY AND COMPLETENESS .4. ON COMPLETENESS FORW[P] AND PSPACE ANALOGS, Annals of pure and applied Logic, 73(3), 1995, pp. 235-276
We describe new results in parametrized complexity theory. In particul
ar, we prove a number of concrete hardness results for W[P], the top l
evel of the hardness hierarchy introduced by Downey and Fellows in a s
eries of earlier papers. We also study the parametrized complexity of
analogues of PSPACE via certain natural problems concerning k-move gam
es, Finally, we examine several aspects of the structural complexity o
f W [P] and related classes. For instance, we show that W[P] can be ch
aracterized in terms of the DTIME (2(o(n))) and NP.