Source-linked AI summary
A Proof of the CSP Dichotomy Conjecture
Dmitriy Zhuk
TL;DR
The paper tackles the problem of classifying finite constraint languages as polynomial-time solvable or NP-complete. It presents an algorithm for languages with a weak near-unanimity polymorphism and proves the remaining direction of the dichotomy conjecture. The result resolves the main conjecture, while leaving open whether a truly polynomial algorithm can avoid exponential dependence on domain size.
Problem
The central question is whether every finite constraint language produces a CSP that is either polynomial-time solvable or NP-complete, with WNU preservation characterizing tractability.
Method
The paper develops an algorithm combining local consistency, recursive domain reductions, structural algebraic analysis, and linear-equation solving over prime fields.
Results
Theorem 1.4 proves that CSP(Γ) is polynomial-time solvable when Γ has a WNU preserving it and NP-complete otherwise.
Takeaways & Limitations
The dichotomy conjecture is proved for finite constraint languages with WNU polymorphisms.
Takeaways & Limitations
The algorithm uses detailed algebraic knowledge and depends exponentially on the domain size, leaving open whether a truly polynomial algorithm exists.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper addresses the CSP dichotomy conjecture, which predicts that every finite constraint language yields either a polynomial-time or NP-complete problem. It proves the WNU formulation by giving a polynomial-time algorithm for languages preserved by a WNU operation.
- CSP asks whether variables can be assigned values satisfying specified constraints, and finite constraint languages restrict which relations may appear.
- The dichotomy conjecture states that CSP(Γ) is either solvable in polynomial time or NP-complete.
- The WNU formulation predicts polynomial-time solvability when a WNU preserves Γ and NP-completeness otherwise.
- It suffices to study core languages containing all unary singleton relations and an idempotent WNU.
- The paper presents a polynomial-time algorithm for languages preserved by an idempotent WNU, thereby proving the dichotomy conjecture.
- The paper concludes by discussing open questions and generalizations, including Valued CSP, Infinite Domain CSP, Quantified CSP, and Promise CSP.
2 Outline of the algorithm
The algorithm alternates local consistency, domain reduction, recursive decomposition, and affine reasoning. It maintains an affine relaxation containing all original solutions and progressively tightens it until satisfiability is decided.
- The algorithm uses three main ingredients: structural domain classification, consistency enforcement, and solving linear equations over prime fields.
- After sufficient consistency, domains can be reduced to proper strong subsets without losing all solutions; otherwise domains factor into prime-field products with affine relations.
- For the affine case, A is the original factorized solution set and B is the factorized instance’s solution set, with A ⊆ B computed by Gaussian elimination.
- Recursive checks identify solutions in B that are absent from A, while weakening constraints produces codimension-one affine restrictions or decomposes the instance.
- Worked example: In the Z4 example, factoring modulo 2 and Gaussian elimination yield an affine system whose candidate solutions are tested recursively on smaller domains.
- Worked example: The example derives x′_1 = 1 and x′_3 = 1 as successive affine restrictions, then verifies the remaining candidate solution in the original system.
3 Definitions
The definitions establish the algebraic and CSP terminology used by the paper, including clones, algebras, specialized subuniverses, consistency properties, and structural relations between instances.
- A clone is a set of operations closed under composition and containing all projections.
- An algebra consists of a finite universe together with a family of basic operations; here domains carry a special WNU operation.
- Polynomial completeness means that the clone generated by the algebra’s operations and all constants contains every operation on the universe.
- A linear finite idempotent algebra is isomorphic to a product of prime cyclic fields equipped with addition.
- Absorption means a term operation maps tuples with one arbitrary coordinate and all other coordinates in B back into B.
- CSP instances: CSP instances use variables, domains, and constraints, while paths and projections define connectivity and structural reductions.
- Consistency: Cycle consistency requires 1-consistency and preservation of values around every closed path; linkedness requires paths connecting every pair of domain values.
4 Algorithm
The algorithm repeatedly checks consistency, reduces variable domains while preserving solutions, and solves the remaining linear case over prime fields.
- Main algorithm: Solve iteratively calls AnswerOrReduce, which either returns a solution or a domain reduction, then applies Reduce to continue.The reduction preserves solutions whenever the original instance is satisfiable.
- Main algorithm: AnswerOrReduce checks cycle consistency, irreducibility, and weaker instances before reducing domains or invoking SolveLinearCase.Inconsistent instances can yield no solution or a justified domain restriction.
- Domain reductions: Domains may be reduced to binary absorbing subuniverses, centers, equivalence classes of suitable congruences, or other strong subsets.The reductions are justified by the corresponding correctness theorems.
- Linear case: SolveLinearCase factorizes domains by minimal linear congruences and represents the resulting instance as linear equations over prime fields.Each quotient is a product of prime-field components, and equations only combine variables from the same field.
- Linear case: New equations are added while weakening constraints and recursively testing linked or nonlinked projections; each iteration reduces the solution-space dimension.Because the dimension drops by at least one, the procedure stops in at most r steps.
5 Correctness of the Algorithm
Correctness rests on an algebraic four-way structural decomposition and consistency-preserving reductions. These properties establish both solution preservation and polynomial running time.
- Structural theorem: A finite algebra with a special WNU operation has a binary absorbing subuniverse, center, polynomially complete quotient, or linear quotient over a prime field.This four-way decomposition is derived using the clone generated by the WNU operation and constants.
- Complexity: The algorithm’s recursive depth is less than |A| + |Γ|, and every loop has a polynomial bound.The resulting algorithm is therefore polynomial.
- Auxiliary functions: CheckCycleConsistency returns a correct status: consistency, unsatisfiability, or a domain restriction containing every solution’s value for a variable.Its correctness follows from the final binary relations being subdirect and derived from the original constraints.
- Auxiliary functions: CheckIrreducibility likewise returns a correct irreducibility result, an unsatisfiability result, or a solution-preserving domain restriction.The stated guarantee applies to every returned outcome.
- Solution preservation: For a cycle-consistent irreducible instance, restricting a domain to a nontrivial absorbing subuniverse or center preserves satisfiability.The instance has a solution exactly when it has one using the restricted domain.
- Solution preservation: The same equivalence holds when restricting a domain to a class of a congruence whose quotient is polynomially complete.This handles the polynomially complete branch of the structural decomposition.
6 The Remaining Definitions
This section defines the algebraic and structural notions used to analyze CSP instances, coverings, linkedness, and relations with the parallelogram property.
- Algebraic setting: Each CSP domain is treated as a finite algebra with a special WNU operation, and relations are subalgebras of corresponding products.The section fixes this algebraic interpretation for subsequent claims.
- Subuniverses: PC and linear subuniverses are defined through polynomially complete and linear congruences, and together with absorbing and central types form the one-of-four classification.Minimal PC and linear subuniverses are blocks of their corresponding congruences.
- Coverings: Coverings map variables and constraints to an original instance, while expanded coverings additionally permit weaker or equivalent constraints and reflexive constraints.These constructions formalize recursive instance transformations.
- Coverings: Solutions of an original instance expand to solutions of a covering, and expanded coverings preserve cycle consistency and irreducibility.Tree-formula coverings of 1-consistent instances also have subdirect solution sets.
- Linkedness: For a cycle-consistent instance, LinkedCon(Θ,x) connects domain values joined by paths and is a congruence.All connected pairs can be joined by a single path.
7 Absorption, Center, PC Congruence, and Linear Congruence
The section develops structural lemmas for absorbing subuniverses, centers, and polynomially complete (PC) congruences, then uses them to constrain relations and support cycle-consistency reasoning. It also characterizes PC subuniverses and congruences through products and coordinate projections.
- Absorption and center: A pp-formula replacement preserves absorption and center properties when the substituted constraint relations have the corresponding term operations or centers.These closure lemmas transfer algebraic structure through relations defined by primitive-positive formulas.
- Absorption and center: A nontrivial absorbing subuniverse of a product yields a nontrivial absorbing subuniverse in at least one factor, using the same term operation.The proof proceeds by induction on the product arity and restricts to a non-full projection or slice.
- Absorption and center: Centers are absorbing subuniverses, and combinations of centers or absorbing subuniverses rule out corresponding essential relations.The stated consequences include binary, ternary, and higher-arity nonexistence results for essential relations.
- PC congruence: PC congruence structure decomposes through the map ψ into a surjective product of quotient algebras, with PC subuniverses described by unary coordinate constraints.For every nonempty PC subuniverse, a quotient can be chosen in which it is an equivalence class and the factors have no nontrivial binary absorbing subuniverse or center.
- PC congruence: After quotienting by all PC congruences, the resulting algebra has no nontrivial binary absorbing subuniverse or center, and PC subuniverses of products factor coordinatewise.PC congruences on such products are induced by one coordinate, while PC subuniverses are products of PC subuniverses in the factors.
- Linear congruence: In the nonlinear case, the absence of higher-arity essential relations means cycle consistency on binary relations is sufficient to guarantee a solution.The section contrasts this with the linear case, where the relevant obstruction is not eliminated by the same property.
8 Proof of the Auxiliary Statements
This section establishes auxiliary lemmas for reductions, bridges, congruences, and strategies used to analyze CSP instances. These results preserve structural properties, characterize relations through bridges and linear equations, and support termination of the overall process.
- 8.1 One-of-four reductions: One-of-four minimal reductions preserve subuniverse structure, and solutions preserve cycle-consistency and irreducibility when the reduced instance has a solution.The lemmas also show that suitable reduced constraints remain subdirect and that linked elements remain connected under absorbing, central, PC, and nonlinear reductions.
- 8.3 Adding linear variable: Strongly rich relations admit Abelian-group representations, including relations defined by equations such as φ1(a1) + φ2(a2) + φ3(b1) + φ4(b2) = 0.A specialized four-variable relation is further expressed as a1 −a2 −a3 + a4 = 0.
- 8.4 Existence of a bridge: Optimal bridges and critical relations impose strict congruence-extension properties that underpin the structural analysis of linked components.The results include strict enlargement for optimal bridges between different irreducible congruences and for covers of critical relations.
- 8.4 Existence of a bridge: Critical rectangular relations yield irreducible congruences and bridges whose extensions contain endpoint projections or projections of the relation’s cover.For arity greater than two, the associated congruences strictly expand, while the binary case preserves the corresponding congruences.
- 8.4 Existence of a bridge: Bridges compose across cycle-consistent connected instances, producing extensions that contain all pairs linked by the instance and, in some cases, by its covered constraints.For constraints sharing a variable, the extension contains the relation LinkedCon(Θ, x).
- 8.6 Strategies: The auxiliary lemmas ensure that reductions and strategy steps retain nonempty relations under stated subdirectness and nonlinearity conditions, while expansion properties support eventual termination.In particular, Theorem 8.26 propagates nonemptiness between successive reductions, and the population argument rules out indefinite fragmentation.
9 Proof of the Main Theorems
The proof develops successive reductions for cycle-consistent CSP instances and shows how absorbing, central, polynomially complete, and nonlinear cases preserve or characterize solvability. It then derives structural consequences, including affine solution sets, critical relations, and linked components with non-subdirect solution sets.
- 9.1 Existence of a next reduction: Binary absorbing, central, and polynomially complete domain structures each yield a 1-consistent reduction of the current instance.These are the three reduction cases used when constructing the next stage of a strategy.
- 9.3 Theorems from Section 5: Cycle-consistency guarantees a solution when domains contain no quotient that is a nontrivial linear algebra.This is stated as the bounded-width corollary for instances whose domains avoid such linear factors.
- 9.1 Existence of a next reduction: The reduction analysis repeatedly decreases a lexicographic measure or derives contradictions from nonempty intersections, supporting termination and the existence of smaller reductions.The proof also uses bridges between congruences and tree-formula constructions to establish these decreases and contradictions.
- 9.2 Existence of a linked connected component: For a crucial, disconnected instance, an expansion contains a linked connected component whose solution set is not subdirect.This structural conclusion is supplied by Theorem 9.6 and is used alongside reductions and tree-formula arguments in the main proof.
- 9.3 Theorems from Section 5: A nonlinear 1-consistent reduction preserves solvability: any solution of the original instance has a solution within that reduction.This theorem connects nonlinear reductions in the strategy to the existence of solutions in restricted domains.
- 9.2 Existence of a linked connected component: The proof establishes that crucial constraints become critical relations with the parallelogram property and can define subdirect key relations.Related constructions also produce covering instances that preserve unsatisfiability or expose linked components with non-subdirect solution sets.
10 Conclusions
The paper concludes that, although the main problem is resolved, important consequences, open questions, and generalizations of CSP remain.
- The paper discusses consequences of the result, open questions, and possible generalizations of the CSP.
10.1 A general algorithm for the CSP
The paper raises whether CSP-WNU has a polynomial algorithm when the WNU is known to exist but not provided, and notes a fixed-domain approach.
- 10.1 A general algorithm for the CSP: CSP-WNU asks whether a formula whose relations are preserved by some WNU is satisfiable, when only the WNU's existence is known.
- 10.1 A general algorithm for the CSP: The section formulates the existence of a polynomial algorithm for CSP-WNU as an open problem.
- 10.1 A general algorithm for the CSP: For a fixed domain, the paper's algorithm solves CSP-WNU by testing finitely many WNU operations derived from the domain size.
10.2 A simplification of the algorithm.
The paper conjectures that its algorithm can be simplified by removing WeakenEveryConstraint from Solve, potentially reducing recursion depth and complexity.
- 10.2 A simplification of the algorithm.: The authors believe WeakenEveryConstraint can be removed from Solve without consequences.
- 10.2 A simplification of the algorithm.: Whether the algorithm still works after this removal is posed as an open problem.
- 10.2 A simplification of the algorithm.: Removing WeakenEveryConstraint would reduce recursion depth from |A| + |Γ| to |A| and significantly lower complexity.
10.3 A generalization for the nonWNU case.
The paper asks whether its results and ideas extend to constraint languages not preserved by a WNU, including conditions for safely reducing domains to binary absorbing subuniverses.
- 10.3 A generalization for the nonWNU case.: The paper asks whether its results and ideas can apply to constraint languages not preserved by a WNU.
- 10.3 A generalization for the nonWNU case.: It is unclear which assumptions suffice to reduce a domain safely to a binary absorbing subuniverse.
- 10.3 A generalization for the nonWNU case.: Problem 3 asks for the weakest assumptions under which Theorems 5.5 and 5.6 hold.
10.4 Infinite domain CSP
For infinite domains, CSP complexity can become undecidable, but restrictions such as reducts of finitely bounded homogeneous structures restore a setting in which algebraic classification is possible.
- Infinite-domain complexity: CSP(Γ) can express every computational problem under polynomial-time Turing reductions when infinite domains are allowed.This broadens the complexity landscape beyond finite-domain CSP.
- Infinite-domain complexity: CSP(Γ) is undecidable for Γ containing x + y = z, x · y = z, and x = 1 over the integers.Hilbert’s tenth problem can be expressed using these three relations.
- Structural restriction: Assuming Γ is a reduct of a finitely bounded homogeneous structure places the CSP back in NP.The reducts of (Q; <) have a full complexity classification.
10.5 Valued CSP
Valued CSP replaces relational constraints with rational-valued mappings and conjunction with summation, yielding an optimization problem. The CSP dichotomy result consequently characterizes the complexity of all VCSP(Γ).
- Definition: VCSP replaces constraint relations with mappings to rational numbers and conjunction with sums.For finite A and Γ of mappings A → Q ∪ {∞}, instances combine mappings over variables.
- Optimization formulation: A VCSP instance seeks an assignment minimizing a sum of Γ-mappings evaluated on selected variables.The objective is f(x1, . . . , xn) = f1(...) + · · · + fs(...).
- Complexity consequence: The CSP dichotomy conjecture implies a complexity dichotomy for VCSP and characterizes all tractable sets of mappings Γ.The characterization is obtained modulo the CSP Dichotomy Conjecture.
10.6 Quantified CSP
Quantified CSP extends CSP with universal and existential quantifiers, but its complexity can include classes beyond the conjectured trichotomy. Important cases remain unresolved, especially for larger domains and nonidempotent languages.
- Definition: QCSP extends existentially quantified CSP sentences by allowing both universal and existential quantifiers.Its instances have alternating quantifiers followed by a conjunction of relations from Γ.
- Known complexity: The proposed QCSP trichotomy of polynomial time, NP-completeness, or PSpace-completeness was disproved.Counterexamples include coNP-complete, DP-complete, and ΘP_2-complete QCSPs on domains of sizes three, four, and ten.
- Open cases: QCSP complexity remains unknown for higher domains and for the nonidempotent case.The idempotent 3-element case has been classified into tractable, NP-complete, coNP-complete, or PSpace-complete cases.
- Open problems: Two open problems are determining possible QCSP complexity and describing all Γ for which QCSP(Γ) is tractable.The text identifies these as Problems 4 and 5.
10.7 Promise CSP
Promise CSP gives two related instances and asks whether both are satisfiable or both are unsatisfiable under a promise linking their solutions. Its complexity is open even for important small-domain cases.
- Definition: Promise CSP supplies paired relations over domains A and B and compares satisfiability of two corresponding formulas.The promise states that a solution to one instance implies a solution to the other, often via a homomorphism.
- Canonical example: Graph (k, l)-colorability asks whether a graph is k-colorable or not even l-colorable, with k ≤ l.It is the most popular example of Promise CSP.
- Known results: (k, l)-colorability is NP-hard for l = 2k − 1 and k ≥ 3, while the complexity of (3, 6)-colorability remains unknown.The latter is an explicit unresolved case despite the hardness result.
- Boolean case: A dichotomy is known for symmetric Boolean PCSP, but the general two-element-domain problem remains widely open.The unresolved classification asks for the complexity of PCSP(Γ) for all Boolean Γ.
10.8 Surjective CSP
This section introduces Surjective CSP, where solutions must use every element of the domain, and poses complexity questions for a concrete three-element language and general constraint languages.
- Surjective CSP asks whether a formula over a constraint language has a solution assigning every domain element to at least one variable.The domain elements must all appear among the variable assignments.
- The section uses this concrete three-element problem as a starting point before addressing the complexity of Surjective CSP for all constraint languages.Only few Surjective CSP complexity results were known in the cited discussion.
- For A = {a, b, c}, the no-rainbow problem asks for the complexity of SurjCSP({R}) with R containing triples that omit at least one domain element.R = {(x, y, z) | {x, y, z} ≠ A}.