Parameterized complexity classes beyond para-NP

DOI10.1016/J.JCSS.2017.02.002MaRDI QIDQ2396719zbMATH OpenOpenAlexFDO

Authors Ronald de Haan, Stefan Szeider

Publication date 24 May 2017

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1016/j.jcss.2017.02.002

zbMATH Keywords

parameterized complexitypolynomial hierarchyfpt-reductionsWeft-hierarchy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Machine characterizations for parameterized complexity classes beyond para-NP
• Describing parameterized complexity classes
• scientific article; zbMATH DE number 2086399
• scientific article; zbMATH DE number 1161563
• Parameterized complexity and subexponential-time computability
• Parameterized Complexity Classes under Logical Reductions
• Parameterized computation and complexity: a new approach dealing with NP-hardness
• On the space and circuit complexity of parameterized problems: classes and completeness
• On the structure of parameterized problems in NP

Cites work

• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 3904558 (Why is no real title available?)
• scientific article; zbMATH DE number 25190 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 5493266 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Anatomy and empirical evaluation of modern SAT solvers
• Complete sets and the polynomial-time hierarchy
• Complexity of judgment aggregation
• Computational Complexity
• Computational Complexity
• Describing parameterized complexity classes
• Fixed-parameter complexity in AI and nonmonotonic reasoning
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Fixed-parameter tractable reductions to SAT
• Fundamentals of parameterized complexity
• Linear completeness thresholds for bounded model checking
• Machine characterizations for parameterized complexity classes beyond para-NP
• On minimal constraint networks
• P, NP, and NP-completeness. The basics of computational complexity.
• Parameterized algorithms
• Parameterized complexity classes beyond para-NP
• Parametrized complexity theory.
• The closure of monadic NP
• The complexity of logic-based abduction
• The polynomial-time hierarchy
• The structure of strategy-proof social choice. I: General characterization and possibility results on median spaces
• Towards an Optimal CNF Encoding of Boolean Cardinality Constraints
• Which problems have strongly exponential complexity?

Cited in

(9)

• The complexity of finding temporal separators under waiting time constraints
• Parametrized complexity: New developments and research frontiers
• Fixed-parameter tractable reductions to SAT
• Machine characterizations for parameterized complexity classes beyond para-NP
• Parameterized Complexity Classes under Logical Reductions
• Parameterized complexity in the polynomial hierarchy. Extending parameterized complexity theory to higher levels of the hierarchy
• The parameterized complexity of motion planning for snake-like robots
• Treewidth with a quantifier alternation revisited
• Parameterized complexity classes beyond para-NP

This page was built for publication: Parameterized complexity classes beyond para-NP

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