Dichotomy Theorem (Constraint Satisfaction)

Definition

Dichotomy Theorem (Constraint Satisfaction)

For every finite domain $D$ and finite constraint language $\Gamma$ over $D$,

$$\mathrm{CSP}[\Gamma ]\in \mathrm{P}\text{or}\mathrm{CSP}[\Gamma ]\text{ is NP-complete}.$$

Here, $\Gamma$ is fixed and $\mathrm{CSP}[\Gamma ]$ contains the CSP instances whose constraint relations belong to $\Gamma$. Moreover, the languages yielding problems in P can be characterised exactly; every other finite language yields an NP-complete problem.

Formerly the Feder–Vardi dichotomy conjecture, the theorem was proved independently by Bulatov and Zhuk.

Intuition

Why the language controls complexity

Fixing $\Gamma$ fixes every kind of local interaction that constraints may impose. An input instance varies only the variables, scopes, and repetitions of those relations:

$$I=(V,D,\{(S_i,R_i){\}}_{i=1}^m),R_i\in \Gamma .$$

If the relations in $\Gamma$ share enough exploitable algebraic structure, all such instances admit a polynomial-time algorithm. Otherwise, they can express an NP-complete problem. The theorem proves that every finite $\Gamma$ falls on one side of this boundary.

Why it matters

The theorem reduces the complexity analysis of infinitely many CSP instances to the finite vocabulary $\Gamma$:

$$\Gamma ⟼\mathrm{CSP}[\Gamma ]\in \mathrm{P}\text{or}\mathrm{CSP}[\Gamma ]\text{ is NP-complete}.$$

This gives three useful consequences:

• one classification covers every instance built from the same relation types;
• no finite-domain, finite-language CSP is NP-intermediate;
• choosing which relations a modelling language permits determines whether its worst-case satisfiability problem is tractable or NP-complete.

Scope and limitations

The theorem gives a complete classification with respect to the constraint language. It fixes a finite set of allowed relations $\Gamma$ and classifies the complexity of all instances built from those relations.

This does not classify every polynomial-time solvable class of CSP instances. Tractability may instead follow from restrictions on the structure of each instance, such as how often variables occur or how constraints overlap, without restricting the relations that may appear.

The theorem also assumes the usual explicit, extensional representation of relations. Practical solvers often represent constraints implicitly and provide global constraints whose concise encoding is much smaller than their table of satisfying tuples. Their complexity must be measured against that concise input representation rather than an expanded relation table.

Example

Bounded variable occurrence

Let ${\mathcal{C}}_1$ contain every CSP instance in which each variable occurs in at most one constraint. Constraint scopes are then pairwise disjoint, so each constraint can be solved independently:

$$I\in {\mathcal{C}}_1\text{ is satisfiable}⟺\forall (S,R)\in \mathcal{C}:R\ne \varnothing .$$

Hence ${\mathcal{C}}_1$ is polynomial-time solvable even though no restriction is placed on the constraint language. Its tractability comes from instance structure, not from $\Gamma$.

The global all-different constraint

For variables $x_1,\dots ,x_n$ over a domain $D$ of size $d$, all-different requires

$$\forall i\ne j:x_i\ne x_j.$$

A solver can represent this condition directly. An explicit relation table would instead contain

$$d(d-1)\cdots (d-n+1)=\frac{d!}{(d-n)!}$$

satisfying tuples when $n\le d$, drawn from $d^n$ possible tuples. This can be exponentially larger than the global constraint’s concise description.