Complexity of constraint satisfaction

In constraint satisfaction, the complexity of constraint satisfaction has mainly been studied for discriminating between tractable and intractable constraint satisfaction problems from the point of view of computational complexity. In particular, the constraint satisfaction problems mostly analyzed are those on finite domains.

Solving a constraint satisfaction problem on a finite domain is an NP complete problem. Research has shown a number of polynomial-time subcases, some limiting the allowed constraints, some others related to the dual of a constraint satisfaction problem. Research has also established relationship of the constraint satisfaction problem with problems in other areas such as finite model theory and databases.

Constraint satisfaction and the homomorphism problem

A link between constraint satisfaction and database theory has been provided in the form of a correspondence between the problem of constraint satisfiability to the problem of checking whether there exists an homomorphism between two relational structures. A relational structure is a mathematical representation of a database: it is a set of values and a set of relations over these values. Formally, $A=(V,R_{1}^{A},\ldots ,R_{n}^{A})$, where each $R_{i}^{A}$ is a relation over $V$, that is, a set of tuples of values of $V$.

A relational structure is different from a constraint satisfaction problem because a constraint is a relation and a tuple of variables. Also different is the way in which they are used: for a constraint satisfaction problem, finding a satisfing assignment is the main problem; for a relation structure, the main problem is finding the answer to a query.

The constraint satisfaction problem is however related to the problem of establishing the existence of an homomorphism between two relational structures. An homomorphism is a function from the values of the first relation to the values of the second that, when applied to all values of a relation of the first structure, turns it into a subset of the corresponding relation of the second structure. Formally, $h$ is a homomorphism from $A=(V,R_{1}^{A},\ldots ,R_{n}^{A})$ to $B=(D,R_{1}^{B},\ldots ,R_{n}^{B})$ if it is a function from $V$ to $D$ such that, if $(x_{1},\ldots ,x_{k})\in R_{i}^{A}$ then $(h(x_{1}),\ldots ,h(x_{k}))\in R_{i}^{B}$.

A direct correspondence between the constraint satisfaction problem and the homomorphism problem can be established. For a given constraint satisfaction problem, one can build a pair of relational structures, the first encoding the variables and the signatures of constraints, the second encoding the domains and the relations of the constraints. Satisfiability of the constraint satisfaction problem corresponds to finding a value for every variable such that replacing a value in a signature makes it a tuple in the relation of the constraint. This is possible exactly if this evaluation is a homomorphism between the two relational structures.

The inverse correspondence is the opposite one: given two relational structures, one encodes the values of the first in the variables of a constraint satisfaction problem, and the values of the second in the domain of the same problem. For every tuple of every relation of the first structure, there is a constraint having as values the correspondent relation of the first structure. This way, a homomorphism corresponds to mapping every scope of every constraint (every tuple of every relation of the first structure) into a tuple in the relation of the constraint (a tuple in the correponding relation of the second structure).

References

• Dechter, Rina (2003). Constraint processing. Morgan Kaufmann. ISBN 1-55860-890-7
• Vardi, Moshe Y. (2000). Constraint Satisfaction and Database Theory: a Tutorial. PODS 2000. pp. 76–85.