A Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy

We present a list of parameterized problems together with a complexity classification of whether they allow a fixed-parameter tractable reduction to SAT or not. These problems are parameterized versions of problems whose complexity lies at the second level of the Polynomial Hierarchy or higher.

• Publication year

  2019

• Venue

  Algorithms

• Publication date

  2019-09-09

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.3390/A12090188
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• CNF Encodings

  2021cited by this paper
• Parameterized Complexity in the Polynomial Hierarchy: Extending Parameterized Complexity Theory to Higher Levels of the Hierarchy

  2019influential reference
• Parameterized complexity classes beyond para-NP

  2017influential reference
• Parameterized Complexity Results for Symbolic Model Checking of Temporal Logics

  2016influential reference
• Parameterized Complexity Results for the Kemeny Rule in Judgment Aggregation

  2016cited by this paper
• Fixed-Parameter Tractable Reductions to SAT for Planning

  2015cited by this paper
• Parameterized Complexity Results for Agenda Safety in Judgment Aggregation

  2015influential reference
• An Overview of Non-Uniform Parameterized Complexity

  2015cited by this paper
• Machine Characterizations for Parameterized Complexity Classes Beyond Para-NP

  2015influential reference
• Fixed-Parameter Tractable Reductions to SAT

  2014influential reference
• Boolean satisfiability

  2014cited by this paper
• Backdoors to Normality for Disjunctive Logic Programs

  2013cited by this paper
• Minimal Sets over Monotone Predicates in Boolean Formulae

  2013cited by this paper
• Fundamentals of Parameterized Complexity

  2013cited by this paper
• Backdoors to Abduction

  2013cited by this paper
• The Parameterized Complexity of Reasoning Problems Beyond NP

  2013influential reference
• Robust Constraint Satisfaction and Local Hidden Variables in Quantum Mechanics

  2013influential reference
• Complexity-sensitive decision procedures for abstract argumentation

  2012cited by this paper
• Towards efficient MUS extraction

  2012cited by this paper
• Complexity of Judgment Aggregation

  2012cited by this paper
• Answer set programming at a glance

  2011cited by this paper
• The Logic Programming Paradigm: A 25-Year Perspective

  2011cited by this paper
• On minimal constraint networks

  2011cited by this paper
• Bounded Model Checking

  2009influential reference
• Computational Complexity: A Modern Approach

  2009cited by this paper
• Principles of model checking

  2008cited by this paper
• Completeness in the Polynomial-Time Hierarchy A Compendium ∗

  2008cited by this paper
• The structure of strategy-proof social choice - Part I: General characterization and possibility results on median spaces

  2007cited by this paper
• Invitation to fixed-parameter algorithms

  2007cited by this paper
• Closures and dichotomies for quantified constraints

  2006cited by this paper
• Parameterized Complexity Theory

  2006cited by this paper
• Compendium of Parameterized Problems

  2006cited by this paper
• Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series)

  2006cited by this paper
• Resolve and Expand

  2004cited by this paper
• Quantified Constraint Satisfaction and Bounded Treewidth

  2004cited by this paper
• QUBOS: Deciding Quantified Boolean Logic Using Propositional Satisfiability Solvers

  2002cited by this paper
• Describing parameterized complexity classes

  2002cited by this paper
• SIGACT news complexity theory comun 37

  2002cited by this paper
• Approximability and completeness in the polynomial hierarchy

  2000cited by this paper
• The Closure of Monadic NP

  2000cited by this paper
• Symbolic Model Checking without BDDs

  1999cited by this paper
• Stable models and an alternative logic programming paradigm

  1998cited by this paper
• Parameterized Complexity

  1998influential reference
• Model checking

  1996cited by this paper
• COMPLEXITY RESULTS FOR SAS+ PLANNING

  1995cited by this paper
• Treewidth: Computations and Approximations

  1994cited by this paper
• A linear time algorithm for finding tree-decompositions of small treewidth

  1993cited by this paper
• The complexity of logic-based abduction

  1993cited by this paper
• On Truth-Table Reducibility to SAT

  1991cited by this paper
• Classical negation in logic programs and disjunctive databases

  1991cited by this paper
• The Boolean hierarchy and the polynomial hierarchy: a closer connection

  1990cited by this paper
• On the Composition of Zero-Knowledge Proof Systems

  1990cited by this paper
• ADL: Exploring the Middle Ground Between STRIPS and the Situation Calculus

  1989cited by this paper
• The polynomial time hierarchy collapses if the Boolean hierarchy collapses

  1988cited by this paper
• The Boolean Hierarchy I: Structural Properties

  1988cited by this paper
• The Strong Exponential Hierarchy Collapses

  1987cited by this paper
• On the Complexity of Derivation in Propositional Calculus

  1983cited by this paper
• The Polynomial-Time Hierarchy

  1976influential reference
• Complete Sets and the Polynomial-Time Hierarchy

  1976influential reference
• The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space

  1972influential reference
• The complexity of theorem-proving procedures

  1971cited by this paper

• Reconstructing Sets of Strings from Their k-Way Projections: Algorithms & Complexity - (Extended Abstract)

  2025cites this paper
• A Note on the Parameterised Complexity of Coverability in Vector Addition Systems

  2025cites this paper
• On Kernelization with Access to NP-Oracles

  2025cites this paper
• Colored Cut Games

  2022cites this paper
• Fixed-Parameter Tractability

  2021cites this paper
• Clustering-Based Binarization Methods Applied to the Crow Search Algorithm for 0/1 Combinatorial Problems

  2020cites this paper
• Treewidth with a Quantifier Alternation Revisited

  2018cites this paper
• Parameterized complexity classes beyond para-NP

  2017cites this paper
• 2 Treewidth with a Quantifier Alternation Revisited

  2017cites this paper
• On the Parameterized Complexity of Belief Revision

  2015cites this paper