Research Frontier and Sourcing

The Algebraic Approach to Constraint Satisfaction

Every finite-template constraint satisfaction problem is in P or is NP-complete, with nothing in between, and which one is decided by whether the template's polymorphism algebra satisfies a Mal'cev condition.

Engineering · Mathematics5 min readKV-MATH-0260

NoteBeyond the source text

This page covers developments that postdate the 1981 source. It is included because it is the direct continuation of themes the source raises, and is marked so its provenance stays legible.

Learning objectives

Define the constraint satisfaction problem over a fixed template.
Define polymorphisms and the Galois connection with relations.
State the dichotomy conjecture and what it excludes.
State the algebraic criterion separating the two cases.
Recount the resolution and who obtained it.
See this as the vindication of the source's applied universal algebra prediction.

01The problem

Fix a finite relational structure — the template. The constraint satisfaction problem for that template asks whether a given instance admits a homomorphism into it.

CSP(B): given a finite structure A, is there a homomorphism A → B?

The template B is fixed; the input is A. Different templates give different computational problems, all in NP.

Familiar problems as CSPs
Template	Problem	Complexity
Complete graph on 2 vertices	2-colouring	in P
Complete graph on 3 vertices	3-colouring	NP-complete
Boolean template for 2-SAT	2-SATISFIABILITY	in P
Boolean template for 3-SAT	3-SATISFIABILITY	NP-complete
Linear equations over a finite field	solvability of a linear system	in P
Horn clauses	HORN-SAT	in P

The tractable cases look heterogeneous — graph colouring, linear algebra, Horn resolution — and the achievement of the algebraic programme was to show they are the same phenomenon.

02Polymorphisms

A polymorphism of a relational structure is an operation on its universe preserving every relation. The polymorphisms form a clone, and that clone is the algebraic invariant of the template.

f : Bⁿ → B is a polymorphism of r ⊆ B^m iff
applying f coordinatewise to n tuples of r yields a tuple of r

Exactly the condition that r is a subuniverse of the n-th power of the algebra ⟨B, f⟩. Polymorphisms and relations are polarities of a Galois connection.

Key resultThe operation–relation Galois connection

Polymorphisms of a set of relations and invariant relations of a set of operations are the two polarities of a Galois connection. The closed sets are clones on one side and relational clones on the other. This is the same machinery Pixley's theorem uses, applied to a computational problem.

The key insight of the programme is that the complexity of CSP(B) depends only on the polymorphism clone of B. Two templates with the same polymorphisms give polynomial-time-equivalent problems, so the classification is an algebraic one.

03The dichotomy conjecture

1978
Schaefer's theorem
For Boolean templates — two-element universes — every CSP is in P or NP-complete, with an explicit list of the six tractable cases. A dichotomy in the smallest case.
1993–1998
Feder and Vardi
Conjectured the dichotomy holds for every finite template: CSP(B) is in P or NP-complete, with nothing in between. Notable because Ladner's theorem guarantees intermediate problems exist in NP generally — so the conjecture asserts CSPs avoid them.
2000s
The algebraic reformulation
Bulatov, Jeavons, Krokhin and others recast the conjecture in terms of polymorphism clones, converting a complexity question into a Mal'cev-condition question.
2017
Resolution
Bulatov and Zhuk independently announced proofs of the dichotomy, by different methods. The conjecture became a theorem.

Key resultWhat the dichotomy excludes

Ladner's theorem says that if P ≠ NP there are problems in NP that are neither in P nor NP-complete. The dichotomy theorem says no CSP over a finite template is such a problem. That is a strong structural statement about a natural class of problems, and it is why the result attracted attention well outside universal algebra.

04The algebraic criterion

The line between tractable and NP-complete is drawn by a Mal'cev condition on the polymorphism algebra.

ProcedureThe dichotomy criterion

in: finite template B → out: P or NP-complete, decidably

input: finite template B (a core, without loss of generality)
form the algebra A(B) whose operations are the polymorphisms of B
check whether A(B) has a Taylor polymorphism
equivalently, a weak near-unanimity (WNU) operation
equivalently, the associated variety omits type 1
if YES: CSP(B) is solvable in polynomial time
if NO: CSP(B) is NP-complete
the condition is decidable, since it is a finite search on a finite algebra

The criterion is a Mal'cev condition of exactly the kind Chapter II introduces. Caveat: 'core' means the template has no proper retract — every template reduces to a core without changing the problem.

A weak near-unanimity operation is an n-ary operation w satisfying w(y,x,…,x) ≈ w(x,y,x,…,x) ≈ ⋯ ≈ w(x,…,x,y) together with idempotency. It is a Mal'cev condition in precisely the sense of Chapter II §12, and the absence of one is exactly the presence of tame congruence type 1.

05Why this vindicates the source

The source's preface predicts that applied universal algebra will become much more prominent, on the evidence of Chapter III's two examples. The CSP programme is the largest instance of that prediction.

The method is Chapter III's method
Take a combinatorial or computational structure, find an algebraic encoding, and let the algebra do the classifying. Kleene's theorem and the syntactic monoid are the same move.
The tools are Chapter II's tools
Mal'cev conditions, clones, the operation–relation Galois connection, varieties. All present in the source, applied to a problem posed a decade later.
The refinement is post-source
Tame congruence theory supplies the type analysis that makes the criterion tractable, and it is a 1988 development.
The scale is new
A complete complexity classification of a natural class of computational problems, obtained by algebraic means. Nothing of this scope existed in 1981.

CautionThis page postdates the source entirely

The Feder–Vardi conjecture was posed more than a decade after the text and resolved more than three decades after it. Nothing here is in Burris and Sankappanavar. It is included because the source's own Section 6, Applications to Computer Science, points in this direction and is now the most dated part of the book.

Frequently asked

Is the dichotomy criterion practical to check?

It is decidable — searching for a weak near-unanimity polymorphism on a finite template is a finite search — and UACalc and related tools implement it. The cost grows quickly, so it is practical for small templates and expensive for larger ones.

Does the dichotomy extend to infinite templates?

No. The theorem is for finite templates. Infinite-domain CSP is an active area with a substantially different theory, and no general dichotomy is known or expected in that setting.

Why does the template need to be a core?

Because a template with a proper retract gives the same problem as its retract, so the classification would otherwise be stated for redundant data. Restricting to cores makes the algebraic criterion well posed, and every template reduces to a core in a way that preserves the problem.

Sources and further reading

S. Burris and H. P. Sankappanavar, A Course in Universal Algebra, Millennium Edition (a corrected re-typesetting of Springer GTM 78, 1981).
G. Grätzer, Universal Algebra, 2nd edition, Springer.
R. McKenzie, G. McNulty and W. Taylor, Algebras, Lattices, Varieties, Volume I.

Original KEVOS® explanatory article. Written from the topic map of the cited works; no text is reproduced from them.