Quantified constraint satisfaction and the polynomially generated powers property
From MaRDI portal
Publication:539977
DOI10.1007/s00012-011-0125-4zbMath1216.68124OpenAlexW2046586055MaRDI QIDQ539977
Publication date: 1 June 2011
Published in: Algebra Universalis (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00012-011-0125-4
Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Classical first-order logic (03B10)
Related Items
Quantified Constraints in Twenty Seventeen, Decomposing Quantified Conjunctive (or Disjunctive) Formulas, The size of generating sets of powers, The Complexity of Quantified Constraints Using the Algebraic Formulation, The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The expressive rate of constraints
- Capturing complexity classes by fragments of second-order logic
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- On the algebraic structure of combinatorial problems
- Resolution for quantified Boolean formulas
- Complexity Classifications of Boolean Constraint Satisfaction Problems
- The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- Varieties with few subalgebras of powers
- Closure properties of constraints
- Constraint Satisfaction Problems of Bounded Width
- Computer Science Logic
- Generalized Majority-Minority Operations are Tractable
- On tractability and congruence distributivity
- Classifying the Complexity of Constraints Using Finite Algebras
- Computer Science Logic
- The complexity of satisfiability problems
- A Simple Algorithm for Mal'tsev Constraints