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


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



    Upload a copy of this work     Papers currently archived: 86,592

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

On the complexity of Gödel's proof predicate.Yijia Chen & Jörg Flum - 2010 - Journal of Symbolic Logic 75 (1):239-254.
Completeness: from Gödel to Henkin.Maria Manzano & Enrique Alonso - 2014 - History and Philosophy of Logic 35 (1):1-26.
Presuppositional completeness.Wojciech Buszkowski - 1989 - Studia Logica 48 (1):23 - 34.
Some kinds of modal completeness.J. F. A. K. Benthem - 1980 - Studia Logica 39 (2-3):125 - 141.
Axiomatic Quantum Mechanics and Completeness.Carsten Held - 2008 - Foundations of Physics 38 (8):707-732.
The importance of physicalism in the philosophy of religion.Leonard Angel - 2010 - International Journal for Philosophy of Religion 67 (3):141 - 156.


Added to PP

16 (#744,048)

6 months
3 (#344,247)

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