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 (5)
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
This page was built for publication: Quantified constraint satisfaction and the polynomially generated powers property
