Math 2.0

General algebraic systems Clones and operations Theorem

CSP dichotomy theorem

Builds on Relational structureHomomorphismPolymorphism of a relationTaylor term

Statement

Let 𝔹\mathbb{B} be a finite relational structure with finitely many relations. The problem CSP(𝔹)\mathrm{CSP}(\mathbb{B}) takes as input a finite structure 𝔸\mathbb{A} of the same signature and asks whether there is a homomorphism from 𝔸\mathbb{A} to 𝔹\mathbb{B}. A finite structure is a core if each of its endomorphisms is an automorphism. Let ℂ\mathbb{C} be the core of 𝔹\mathbb{B}, that is, a core that admits homomorphisms 𝔹→ℂ\mathbb{B} \to \mathbb{C} and ℂ→𝔹\mathbb{C} \to \mathbb{B}; it is unique up to isomorphism. A Taylor polymorphism of ℂ\mathbb{C} is a polymorphism tt of ℂ\mathbb{C} of some arity n≥2n \ge 2 that is a Taylor operation. That is, t(x,…,x)=xt(x, \ldots, x) = x for all xx. Also, for each position i≤ni \le n, tt satisfies an identity t(u1,…,un)≈t(v1,…,vn)t(u_1, \ldots, u_n) \approx t(v_1, \ldots, v_n) with each uj,vj∈{x,y}u_j, v_j \in \set{x, y}, ui=xu_i = x and vi=yv_i = y. Then exactly one of the following holds.

  1. ℂ\mathbb{C} has a Taylor polymorphism, and CSP(𝔹)\mathrm{CSP}(\mathbb{B}) is solvable in polynomial time.
  2. ℂ\mathbb{C} has no Taylor polymorphism, and CSP(𝔹)\mathrm{CSP}(\mathbb{B}) is NP-complete.

In particular, each such constraint satisfaction problem is either in P or NP-complete.

Remarks

The two algebraic cases exclude each other. The two complexity outcomes are different only if P≠NP\mathrm{P} \ne \mathrm{NP}. The hardness half was proved earlier in the algebraic approach to constraint satisfaction. Without a Taylor polymorphism, the polymorphism clone of the core allows a reduction from an NP-complete problem such as 3-colouring. The tractability half was proved independently by Andrei Bulatov and by Dmitriy Zhuk, with two different polynomial-time algorithms. This settled the Feder–Vardi dichotomy conjecture. By a theorem of Siggers, a finite core has a Taylor polymorphism exactly when it has an idempotent 6-ary polymorphism ss of a special form. This ss satisfies s(x,y,x,z,y,z)=s(y,x,z,x,z,y)s(x, y, x, z, y, z) = s(y, x, z, x, z, y) for all x,y,zx, y, z; see Siggers term.

Example: let 𝔹=Kn\mathbb{B} = K_n be the complete graph on nn vertices. Then CSP(Kn)\mathrm{CSP}(K_n) is the nn-colouring problem. For n=2n = 2, the majority operation on the two vertices is a polymorphism and a Taylor operation. So 22-colouring is in P. For n≥3n \ge 3 the graph KnK_n is a core with no Taylor polymorphism, and nn-colouring is NP-complete. More generally, let HH be a finite undirected graph. Then CSP(H)\mathrm{CSP}(H) is in P if HH is bipartite or has a loop, and NP-complete otherwise (Hell and Nešetřil).

Passing to the core matters, because a Taylor polymorphism must be idempotent. For example, the disjoint union of K3K_3 and a single vertex with a loop has no Taylor polymorphism. Its core is the looped vertex, which has one, and indeed its CSP is trivial: every input maps to the loop.

Going deeper

For a student

The polymorphisms of 𝔹\mathbb{B} form a clone, and the complexity of CSP(𝔹)\mathrm{CSP}(\mathbb{B}) depends only on the identities that this clone satisfies. The Taylor condition is the weakest nontrivial such identity, and by the cyclic term and Siggers term theorems it can be tested by a single identity. Earlier special cases include Schaefer's theorem for Boolean structures and the Hell–Nešetřil theorem for undirected graphs. For infinite templates, and for counting or optimisation versions, separate classification programs exist.

Reading path

To understand this page from the ground up, read these 5 pages in order. The foundations come first.

Show the path as a graph
Homomorphism, concept, no evidence levelHomomorphismconceptPolymorphism of a relation, concept, no evidence levelPolymorphism of a rel…conceptRelational structure, concept, no evidence levelRelational structureconceptTaylor term, concept, no evidence levelTaylor termconceptCSP dichotomy theorem, statement, no evidence levelCSP dichotomy theoremstatement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Homomorphism concept
  2. Polymorphism of a relation concept
  3. Relational structure concept
  4. Taylor term concept
  5. CSP dichotomy theorem statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Constraint_satisfaction_problem
About this page
TagZA4YXJ9T1P
URIm2://ZA4YXJ9T1P
Kindstatement, theorem
WritingW0 stub
MSC08A70, 68Q25, 08A40
StatusThis copy of the site has no build data. Run m2 status ZA4YXJ9T1P.
AboutAlgebraic approach to constraint satisfaction
UsesRelational structure, Homomorphism, Polymorphism of a relation, Taylor term
Changed2 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.