4 - Constraint satisfaction problems

Summary

An important class of NP-complete problems is that of constraint satisfaction problems (CSPs), which have been widely investigated and where a phase transition has been found to occur (Williams and Hogg, 1994; Smith and Dyer, 1996; Prosser, 1996). Constraint satisfaction problems are the analogue of SAT problems in first-order logic; actually, any finite CSP instance can be transformed into a SAT problem in an automatic way, as will be described in Section 8.4.

Formally, a finite CSP is a triple (X, R, D). Here X = {x_i|1 ≤ i ≤ n} is a set of variables and R = {R_h, 1 ≤ h ≤ m} is a set of relations, each defining a constraint on a subset of variables in X; D = {D_i|1 ≤ i ≤ n} is a set of variable domains D_i such that every variable x_i takes values only in the D_i, whose cardinality |D_i| equals d_i. The constraint satisfaction problem consists in finding an assignment in D_i for each variable x_i ∈ X that satisfies all relations in R.

In principle a relation R_h may involve any proper or improper subset of X. Nevertheless, most authors restrict investigation to binary constraints, defined as relations over two variables only. This restriction does not affect the generality of the results that can be obtained because any relation of arity higher than two can always be transformed into an equivalent conjunction of binary relations.