A proof of the CSP dichotomy conjecture
From MaRDI portal
Abstract: Many natural combinatorial problems can be expressed as constraint satisfaction problems. This class of problems is known to be NP-complete in general, but certain restrictions on the form of the constraints can ensure tractability. The standard way to parameterize interesting subclasses of the constraint satisfaction problem is via finite constraint languages. The main problem is to classify those subclasses that are solvable in polynomial time and those that are NP-complete. It was conjectured that if a constraint language has a weak near unanimity polymorphism then the corresponding constraint satisfaction problem is tractable, otherwise it is NP-complete. In the paper we present an algorithm that solves Constraint Satisfaction Problem in polynomial time for constraint languages having a weak near unanimity polymorphism, which proves the remaining part of the conjecture.
Recommendations
Cited in
(only showing first 100 items - show all)- A combinatorial constraint satisfaction problem dichotomy classification conjecture
- Constraint satisfaction problems: complexity and algorithms
- From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
- Sandwiches for promise constraint satisfaction
- Galois connections for patterns: an algebra of labelled graphs
- Beyond PCSP (\textbf{1-in-3}, \textbf{NAE})
- On a stronger reconstruction notion for monoids and clones
- On regularity of Max-CSPs and Min-CSPs
- Homogeneous structures: model theory meets universal algebra. Abstracts from the workshop held January 3--9, 2021 (online meeting)
- Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity
- Complexity of correspondence \(H\)-colourings
- The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
- Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms
- Constraint satisfaction problems over semilattice block Mal'tsev algebras
- The number of clones determined by disjunctions of unary relations
- Correspondence homomorphisms to reflexive graphs
- Recolouring homomorphisms to triangle-free reflexive graphs
- General lower bounds and improved algorithms for infinite-domain CSPs
- scientific article; zbMATH DE number 1670830 (Why is no real title available?)
- Complexity of conservative constraint satisfaction problems
- scientific article; zbMATH DE number 5999552 (Why is no real title available?)
- scientific article; zbMATH DE number 4162262 (Why is no real title available?)
- 2 -Way vs.d -Way Branching for CSP
- Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NP-Complete
- The property of being polynomial for Mal’tsev constraint satisfaction problems
- On the Computational Complexity of Monotone Constraint Satisfaction Problems
- scientific article; zbMATH DE number 5531977 (Why is no real title available?)
- The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Correlation decay and tractability of CSPs
- Proof Complexity Meets Algebra
- A dichotomy for first-order reducts of unary structures
- The language of stratified sets is confluent and strongly normalising
- scientific article; zbMATH DE number 7378350 (Why is no real title available?)
- The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
- Universal algebraic methods for constraint satisfaction problems
- Universal Horn Sentences and the Joint Embedding Property
- The lattice and semigroup structure of multipermutations
- When symmetries are not enough: a hierarchy of hard constraint satisfaction problems
- CC-circuits and the expressive power of nilpotent algebras
- Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
- Ideal membership problem over 3-element CSPs with dual discriminator polymorphism
- Time complexity of constraint satisfaction via universal algebra
- Counting restricted homomorphisms via Möbius inversion over matroid lattices
- CSP gaps and reductions in the lasserre hierarchy
- Constant-query testability of assignments to constraint satisfaction problems
- A Dichotomy Theorem for Typed Constraint Satisfaction Problems
- Strong subalgebras and the constraint satisfaction problem
- Computational Short Cuts in Infinite Domain Constraint Satisfaction
- The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
- The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation
- CLAP: A New Algorithm for Promise CSPs
- Topology and Adjunction in Promise Constraint Satisfaction
- Periodic constraint satisfaction problems: polynomial-time algorithms
- The 2-colouring problem for $(m,n)$-mixed graphs with switching is polynomial
- The smallest hard trees
- The algebraic structure of the densification and the sparsification tasks for CSPs
- Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random
- \((\mathbb{Z},\mathrm{succ},U)\), \((\mathbb{Z},E,U)\), and their CSP's
- Constraint satisfaction problem: what makes the problem easy
- Mixing is hard for triangle-free reflexive graphs
- On guarded extensions of MMSNP
- Solving infinite-domain CSPs using the patchwork property
- The complexity of the matroid homomorphism problem
- Computing a partition function of a generalized pattern-based energy over a semiring
- scientific article; zbMATH DE number 7716602 (Why is no real title available?)
- Towards a dichotomy for the list switch homomorphism problem for signed graphs
- Quantaloidal approach to constraint satisfaction
- SDPs and robust satisfiability of promise CSP
- Approximate graph colouring and the hollow shadow
- Generalisations of matrix partitions: complexity and obstructions
- On classifying continuous constraint satisfaction problems
- Unifying the three algebraic approaches to the CSP via minimal Taylor algebras
- Conditional dichotomy of Boolean ordered promise CSPs
- Algebraic global gadgetry for surjective constraint satisfaction
- Complexity classification transfer for CSPs via algebraic products
- Graphs of finite algebras: edges, and connectivity
- Smooth approximations and CSPs over finitely bounded homogeneous structures
- Finite algebras with Hom-sets of polynomial size
- Collapsing the bounded width hierarchy for infinite-domain constraint satisfaction problems: when symmetries are enough
- Commutator equations
- Forbidden tournaments and the orientation completion problem
- Complexity theory. Abstracts from the workshop held June 2--7, 2024
- Ivo G. Rosenberg's work on maximal clones and minimal clones
- The complexity of promise constraint satisfaction problem seen from the other side
- Complexity of finite Borel asymptotic dimension
- Promise and infinite-domain constraint satisfaction
- Quantifiers closed under partial polymorphisms
- Network satisfaction problems solved by k-consistency
- On guarded extensions of MMSNP
- Quantum advantage and CSP complexity
- Reconfiguring homomorphisms to reflexive graphs via a simple reduction
- An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments
- Identifying tractable quantified temporal constraints within Ord-Horn
- Homogeneity and homogenizability: hard problems for the logic SNP
- An order out of nowhere: a new algorithm for infinite-domain CSPs
- Solving promise equations over monoids and groups
- Limits of symmetric computation (invited talk)
- _2P vs PSpace dichotomy for the quantified constraint satisfaction problem
- A topological version of Schaefer's dichotomy theorem
This page was built for publication: A proof of the CSP dichotomy conjecture
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5133982)
