The Complexity of Quantified Constraints Using the Algebraic Formulation

DOI10.4230/LIPIcs.MFCS.2017.27zbMath1441.68087arXiv1701.04086OpenAlexW2963678585MaRDI QIDQ5111241

No author found.

Publication date: 26 May 2020

Full work available at URL: https://arxiv.org/abs/1701.04086

zbMATH Keywords

computational complexityconstraint satisfactionuniversal algebraquantified constraints

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Computational aspects of satisfiability (68R07)

Related Items (4)

The algebraic structure of the densification and the sparsification tasks for CSPs ⋮ Constraint satisfaction problem: what makes the problem easy ⋮ The size of generating sets of powers ⋮ The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation

Cites Work

• Quantified constraint satisfaction and the polynomially generated powers property
• The complexity of constraint satisfaction games and QCSP
• The complexity of equality constraint languages
• The size of generating sets of powers
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Meditations on Quantified Constraint Satisfaction
• The Complexity of Positive First-Order Logic without Equality
• The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• From Complexity to Algebra and Back: Digraph Classes, Collapsibility, and the PGP
• The Complexity of General-Valued CSPs
• Classifying the Complexity of Constraints Using Finite Algebras
• Quantified Equality Constraints
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The Complexity of Quantified Constraints Using the Algebraic Formulation