Completeness results for parameterized space classes

DOI10.1007/978-3-319-03898-8_28MaRDI QIDQ2867094zbMATH OpenOpenAlexFDO

Authors Christoph Stockhusen, Till Tantau

Publication date 10 December 2013

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1308.2892, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.764.6872

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: The parameterized complexity of a problem is considered "settled" once it has been shown to lie in FPT or to be complete for a class in the W-hierarchy or a similar parameterized hierarchy. Several natural parameterized problems have, however, resisted such a classification. At least in some cases, the reason is that upper and lower bounds for their parameterized space complexity have recently been obtained that rule out completeness results for parameterized time classes. In this paper, we make progress in this direction by proving that the associative generability problem and the longest common subsequence problem are complete for parameterized space classes. These classes are defined in terms of different forms of bounded nondeterminism and in terms of simultaneous time--space bounds. As a technical tool we introduce a "union operation" that translates between problems complete for classical complexity classes and for W-classes.

Recommendations

• On the space and circuit complexity of parameterized problems: classes and completeness
• On the Space Complexity of Parameterized Problems
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
• On the parameterized complexity of short computation and factorization
• Machine-based methods in parameterized complexity theory

Cited in

(8)

• Closure properties of parametric subcompleteness
• On the space and circuit complexity of parameterized problems: classes and completeness
• Robustness of PSPACE-complete sets
• Nominal automata with name binding
• scientific article; zbMATH DE number 1330444 (Why is no real title available?)
• On the \(n\)-completeness of covering spaces with parameters
• Parameterised counting in logspace
• Parameterised counting in logspace

This page was built for publication: Completeness results for parameterized space classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2867094)