The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation

DOI10.1145/3568397OpenAlexW3176180680MaRDI QIDQ5875947

No author found.

Publication date: 7 February 2023

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityconstraint satisfactionlogicuniversal algebraquantified constraints

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• QCSP on Partially Reflexive Forests
• The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case
• From Complexity to Algebra and Back: Digraph Classes, Collapsibility, and the PGP
• The Complexity of Quantified Constraints Using the Algebraic Formulation
• A Proof of the CSP Dichotomy Conjecture
• QCSP monsters and the demise of the chen conjecture
• The Complexity of General-Valued CSPs
• Quantified Equality Constraints
• Logical Approaches to Computational Barriers

This page was built for publication: The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation