Parameterized complexity classes beyond para-NP

DOI10.1016/J.JCSS.2017.02.002zbMATH Open1370.68146OpenAlexW2606518309MaRDI QIDQ2396719FDOQ2396719

Authors: Ronald de Haan, Stefan Szeider 

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

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

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)

Cites Work

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

Cited In (8)

• The Parameterized Complexity of Motion Planning for Snake-Like Robots
• Parametrized complexity: New developments and research frontiers
• Fixed-parameter tractable reductions to SAT
• Title not available (Why is that?)
• Parameterized Complexity Classes under Logical Reductions
• Machine characterizations for parameterized complexity classes beyond para-NP
• The complexity of finding temporal separators under waiting time constraints
• 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)