Quantified Constraint Satisfaction and the Polynomially Generated Powers Property
From MaRDI portal
Publication:3519502
DOI10.1007/978-3-540-70583-3_17zbMath1155.68404OpenAlexW1593017268MaRDI QIDQ3519502
Publication date: 19 August 2008
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-70583-3_17
Analysis of algorithms and problem complexity (68Q25) Logic in computer science (03B70) Applications of universal algebra in computer science (08A70)
Related Items
A new line of attack on the dichotomy conjecture, On the growth of generating sets for direct powers of semigroups., The size of generating sets of powers
Cites Work
- 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
- 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
- Generalized Majority-Minority Operations are Tractable
- On tractability and congruence distributivity
- Classifying the Complexity of Constraints Using Finite Algebras
- Tractability and Learnability Arising from Algebras with Few Subpowers
- Computer Science Logic
- The complexity of satisfiability problems
- A Simple Algorithm for Mal'tsev Constraints
- Unnamed Item
- Unnamed Item