Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
type: Item
instance of: scholarly article
title: Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
zbMATH Open document ID: 0828.68077
DOI: 10.1016/0168-0072(94)00034-Z
author: Karl A. Abrahamson
author: Michael R. Fellows
author: Rodney G. Downey
published in: Annals of Pure and Applied Logic
publication date: 1995-07-26T00:00:00Z
review text: The paper devices some new results in parametrized complexity theory. In particular, it is proved that 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. This hierarchy for fixed-parameter problems is based on the logical depth needed to describe the respective problem in terms of circuits. Furthermore, analogs of PSPACE are studied in the fixed-parameter setting. This is done via certain problems concerning \(k\)-move games. Several aspects of the structural complexity of W[P] and related classes are studied. The class W[P] is characterized in terms of DTIME \((2^{o(n)})\) and NP.
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 768743
zbMATH Keywords: parametrized complexity theory
Wikidata QID: Q56620260
MaRDI profile type: Publication
cites work: Q4281539
cites work: Nondeterminism within $P^ * $
cites work: Advice classes of parametrized tractability
cites work: Q4764103
cites work: Q4027320
cites work: Fixed-Parameter Tractability and Completeness I: Basic Results
cites work: Fixed-parameter tractability and completeness II: On completeness for W[1]
cites work: Q4281497
cites work: Q4850549
cites work: Q4501141
cites work: A Combinatorial Problem Which Is Complete in Polynomial Space
cites work: Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
cites work: Q4279511
cites work: The Rectilinear Steiner Tree Problem is $NP$-Complete
cites work: Q4198056
cites work: Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
cites work: Planar Formulae and Their Uses
cites work: Graph minors. XIII: The disjoint paths problem
cites work: Graph minors. XX: Wagner's conjecture
cites work: On the complexity of some two-person perfect-information games
cites work: Parameterized circuit complexity and the \(W\) hierarchy
DBLP publication ID: journals/apal/AbrahamsonDF95
description: scientific article; zbMATH DE number 768743