Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogues

Annals of Pure and Applied Logic 73 (3):235-276 (1995)
  Copy   BIBTEX

Abstract

We describe new results in parametrized complexity theory. In particular, we prove 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. We also study the parametrized complexity of analogues of PSPACE via certain natural problems concerning k-move games. Finally, we examine several aspects of the structural complexity of W [P] and related classes. For instance, we show that W[P] can be characterized in terms of the DTIME ) and NP

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,854

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Context-sensitive transitive closure operators.Iain A. Stewart - 1994 - Annals of Pure and Applied Logic 66 (3):277-301.
An Analysis of the W -Hierarchy.Yijia Chen, Jörg Flum & Martin Grohe - 2007 - Journal of Symbolic Logic 72 (2):513 - 534.
The parameterized complexity of maximality and minimality problems.Yijia Chen & Jörg Flum - 2008 - Annals of Pure and Applied Logic 151 (1):22-61.
Sparse parameterized problems.Marco Cesati & Michael R. Fellows - 1996 - Annals of Pure and Applied Logic 82 (1):1-15.
Mass problems and randomness.Stephen G. Simpson - 2005 - Bulletin of Symbolic Logic 11 (1):1-27.

Analytics

Added to PP
2014-01-16

Downloads
37 (#616,885)

6 months
14 (#240,419)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Sparse parameterized problems.Marco Cesati & Michael R. Fellows - 1996 - Annals of Pure and Applied Logic 82 (1):1-15.

Add more citations

References found in this work

Add more references