Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues (Q1892937): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Created claim: Wikidata QID (P12): Q56620260, #quickstatements; #temporary_batch_1705080783594
Property / Wikidata QID
 
Property / Wikidata QID: Q56620260 / rank
 
Normal rank

Revision as of 18:39, 12 January 2024

scientific article
Language Label Description Also known as
English
Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
scientific article

    Statements

    Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues (English)
    0 references
    0 references
    0 references
    0 references
    26 July 1995
    0 references
    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.
    0 references
    parametrized complexity theory
    0 references

    Identifiers