FIXED-PARAMETER TRACTABILITY AND COMPLETENESS .4. ON COMPLETENESS FORW[P] AND PSPACE ANALOGS

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.