Constraint Language (Constraint Satisfaction)

Definition

Constraint Language (Constraint Satisfaction)

A constraint language $\Gamma$ over a domain $D$ is a set of finite-arity relations on $D$:

$$\Gamma \subseteq \{R\mid \exists r\ge 1:R\subseteq D^r\}.$$

Example

Three-colouring as a restricted CSP

Let

$$D=\{1,2,3\},R_{\ne }=\{(a,b)\in D^2:a\ne b\},{\Gamma }_{3\mathrm{col}}=\{R_{\ne }\}.$$

For a graph $G=(V,E)$, introduce one variable for each vertex and the constraint $((u,v),R_{\ne })$ for each edge $\{u,v\}\in E$. The problem $\mathrm{CSP}[{\Gamma }_{3\mathrm{col}}]$ then asks whether the input graph has a proper three-colouring. The graph changes between instances; the allowed relation $R_{\ne }$ does not.