Math 2.0

Computer science Computational complexity: resources and classes Problem

Constraint satisfaction problem

Builds on Graph homomorphismPNP-completenessNP

Problem

Let DD be a finite set, the domain. Let Γ\Gamma be a finite set of relations on DD, each a subset of DkD^k for some arity k≥1k \ge 1. An instance of CSP(Γ)\mathrm{CSP}(\Gamma) consists of a finite set VV of variables and a finite list of constraints. Each constraint is a pair ((v1,…,vk),R)((v_1, \dots, v_k), R) with v1,…,vk∈Vv_1, \dots, v_k \in V and R∈ΓR \in \Gamma of arity kk. The constraint satisfaction problem CSP(Γ)\mathrm{CSP}(\Gamma) asks whether some map s ⁣:V→Ds \colon V \to D satisfies every constraint, that is, (s(v1),…,s(vk))∈R(s(v_1), \dots, s(v_k)) \in R for each constraint.

Remarks

Every CSP(Γ)\mathrm{CSP}(\Gamma) lies in NP, since an assignment ss is a certificate. Equivalently, CSP(Γ)\mathrm{CSP}(\Gamma) asks whether a given finite relational structure has a homomorphism to the fixed structure (D;Γ)(D; \Gamma).

Example: let D={1,2,3}D = \set{1, 2, 3} and Γ={≠}\Gamma = \set{\ne}, the relation of distinct pairs. Then an instance is a graph, with one constraint for each edge, and CSP(Γ)\mathrm{CSP}(\Gamma) is graph 33-colouring, which is NP-complete. With D={1,2}D = \set{1, 2} instead, the problem is 22-colouring, which lies in P.

Schaefer's dichotomy theorem of 1978 settles the case ∣D∣=2\abs{D} = 2. Tomás Feder and Moshe Vardi conjectured in 1993 that for every finite DD and Γ\Gamma, CSP(Γ)\mathrm{CSP}(\Gamma) is in P or NP-complete. Andrei Bulatov and Dmitriy Zhuk proved this conjecture independently in 2017.

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
Graph homomorphism, concept, no evidence levelGraph homomorphismconceptNP, concept, no evidence levelNPconceptNP-completeness, concept, no evidence levelNP-completenessconceptP, concept, no evidence levelPconceptConstraint satisfaction problem, problem, no evidence levelConstraint satisfacti…problem
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. Graph homomorphism concept
  2. NP concept
  3. NP-completeness concept
  4. P concept
  5. Constraint satisfaction problem problem

Where this leads

1 page builds on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Constraint_satisfaction_problem
About this page
Tag5EHA6R2M6K
URIm2://5EHA6R2M6K
Kindproblem
WritingW0 stub
MSC68Q17, 68Q25
StatusThis copy of the site has no build data. Run m2 status 5EHA6R2M6K.
AboutGraph homomorphism
UsesGraph homomorphism, P, NP-completeness, NP
Same as
Changed3 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

Results about this

Used by