Constraint satisfaction problem: what makes the problem easy
Classical first-order logic (03B10) Logic in computer science (03B70) Complexity of computation (including implicit computational complexity) (03D15) Applications of universal algebra in computer science (08A70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Logic in artificial intelligence (68T27)
Summary: The Constraint Satisfaction Problem is the problem of deciding whether there is an assignment to a set of variables subject to some specified constraints. Systems of linear equations, graph coloring, and many other combinatorial problems can be expressed as Constraint Satisfaction Problems for some constraint language. In 1993 it was conjectured that for any constraint language the problem is either solvable in polynomial time, or NP-complete, and for many years this conjecture was the main open question in the area. After this conjecture was resolved in 2017, we finally can say what makes the problem hard and what makes the problem easy. In the first part of the paper, we give an elementary introduction to the area, explaining how the full classification appeared and why it is formulated in terms of polymorphisms. We discuss what makes the problem NP-hard, what makes the problem solvable by local consistency checking, and explain briefly the main idea of one of the two proofs of the conjecture. The second part of the paper is devoted to the extension of the CSP, called Quantified CSP, where we allow using both universal and existential quantifiers. Finally, we discuss briefly other variants of the CSP, as well as some open questions related to them. For the entire collection see [Zbl 07816357].
- A proof of the CSP dichotomy conjecture
- Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem
- Algebraic approach to promise constraint satisfaction
- Closed systems of functions and predicates
- Complexity classifications of Boolean constraint satisfaction problems
- Computational Complexity
- Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- Constraints, consistency and closure
- CSPs with global modular constraints: algorithms and hardness via polynomial representations
- scientific article; zbMATH DE number 7359806 (Why is no real title available?)
- Meditations on quantified constraint satisfaction
- Monotone monadic SNP and constraint satisfaction
- Non-dichotomies in Constraint Satisfaction Complexity
- Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint
- On the algebraic structure of combinatorial problems
- Polynomial interpolation and the Chinese remainder theorem for algebraic systems
- Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy
- QCSP monsters and the demise of the chen conjecture
- Quantified Constraints in Twenty Seventeen
- Strong subalgebras and the constraint satisfaction problem
- The complexity of constraint satisfaction games and QCSP
- The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case
- The complexity of quantified constraints using the algebraic formulation
- The complexity of satisfiability problems
- The complexity of surjective homomorphism problems-a survey
- The complexity of temporal constraint satisfaction problems
- The computational complexity of disconnected cut and \(2 K_2\)-partition
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The size of generating sets of powers
- The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
- The wonderland of reflections
- Tractability and learnability arising from algebras with few subpowers
- Varieties with few subalgebras of powers
This page was built for publication: Constraint satisfaction problem: what makes the problem easy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6119674)
