Parameterized complexity classes beyond para-NP

DOI10.1016/j.jcss.2017.02.002zbMath1370.68146OpenAlexW2606518309MaRDI QIDQ2396719

Stefan Szeider, Ronald de Haan

Publication date: 24 May 2017

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

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

zbMATH Keywords

polynomial hierarchyparameterized complexityfpt-reductionsWeft-hierarchy

Mathematics Subject Classification ID

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

Related Items (4)

Parameterized complexity classes beyond para-NP ⋮ The Parameterized Complexity of Motion Planning for Snake-Like Robots ⋮ Unnamed Item ⋮ The complexity of finding temporal separators under waiting time constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On minimal constraint networks
• Fundamentals of parameterized complexity
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• The structure of strategy-proof social choice. I: General characterization and possibility results on median spaces
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• The closure of monadic NP
• Fixed-parameter complexity in AI and nonmonotonic reasoning
• Which problems have strongly exponential complexity?
• Describing parameterized complexity classes
• Parameterized complexity classes beyond para-NP
• Parametrized complexity theory.
• P, NP, and NP-Completeness
• Linear Completeness Thresholds for Bounded Model Checking
• Complexity of Judgment Aggregation
• Fixed-Parameter Tractable Reductions to SAT
• Towards an Optimal CNF Encoding of Boolean Cardinality Constraints
• The complexity of logic-based abduction
• Machine Characterizations for Parameterized Complexity Classes Beyond Para-NP
• Computational Complexity
• Parameterized Algorithms
• Computational Complexity

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