Constraint satisfaction problem: what makes the problem easy

DOI10.4171/icm2022/125OpenAlexW4389817267MaRDI QIDQ6119674

Dmitriy N. Zhuk

Publication date: 24 March 2024

Published in: International Congress of Mathematicians (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4171/icm2022/125

zbMATH Keywords

computational complexityconstraint satisfaction problemquantified constraintsCSP dichotomy

Mathematics Subject Classification ID

Logic in artificial intelligence (68T27) Logic in computer science (03B70) Applications of universal algebra in computer science (08A70) Classical first-order logic (03B10) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of surjective homomorphism problems-a survey
• The complexity of constraint satisfaction games and QCSP
• Polynomial interpolation and the Chinese remainder theorem for algebraic systems
• Constraints, consistency and closure
• On the algebraic structure of combinatorial problems
• The wonderland of reflections
• The computational complexity of disconnected cut and \(2 K_2\)-partition
• The size of generating sets of powers
• Closed systems of functions and predicates
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
• Meditations on Quantified Constraint Satisfaction
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Non-dichotomies in Constraint Satisfaction Complexity
• The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case
• Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint
• Varieties with few subalgebras of powers
• The complexity of temporal constraint satisfaction problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Quantified Constraints in Twenty Seventeen
• The Complexity of Quantified Constraints Using the Algebraic Formulation
• Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon
• A Proof of the CSP Dichotomy Conjecture
• QCSP monsters and the demise of the chen conjecture
• CSPs with global modular constraints: algorithms and hardness via polynomial representations
• Algebraic approach to promise constraint satisfaction
• Monotone monadic SNP and constraint satisfaction
• Computational Complexity
• Tractability and Learnability Arising from Algebras with Few Subpowers
• The complexity of satisfiability problems
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)