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

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
Keywords No keywords specified (fix it)
Categories No categories specified
(categorize this paper)
DOI 10.1016/0168-0072(94)00034-z
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 72,607
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Add more references

Citations of this work BETA

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

Add more citations

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 index

Total views
13 ( #775,298 of 2,533,631 )

Recent downloads (6 months)
1 ( #389,998 of 2,533,631 )

How can I increase my downloads?


My notes