Constraint satisfaction problem

From Wikipedia, the free encyclopedia

Constraint satisfaction problems or CSPs are mathematical problems where one must find states or objects that satisfy a number of constraints or criteria. CSPs are the subject of intense research in both artificial intelligence and operations research. Many CSPs require a combination of heuristics and combinatorial search methods to be solved in a reasonable time.

Examples of problems that can be modelled as a constraint satisfaction problem:

Algorithms used for solving constraint satisfaction problems include the AC-3 algorithm, Backtracking, and the min-conflicts algorithm.

1 Formal definition
2 Theoretical aspects of CSPs
3 See also
4 External links

[edit] Formal definition

Formally, a constraint satisfaction problem is defined a triple $\langle X,D,C \rangle$ , where $X$ is a set of variables, $D$ is a domain of values, and $C$ is a set of constraints. Every constraint is in turn a pair $\langle t,R \rangle$ , where $t$ is a tuple of variables and $R$ is a set of tuples of values; all these tuples having the same number of elements; as a result $R$ is a relation. An evaluation of the variables is a function from variables to $v:X \rightarrow D$ . Such an evaluation satisfies a constraint $\langle (x_1,\ldots,x_n),R \rangle$ if $(v(x_1),\ldots,v(x_n)) \in R$ . A solution is an evaluation that satisfies all constraints.

[edit] Theoretical aspects of CSPs

CSPs are also studied in computational complexity theory and finite model theory. An important question is whether for each set of relations, the set of all CSPs that can be represented using only relations chosen from that set is either in PTIME or otherwise NP-complete (assuming P ≠ NP). If such a dichotomy is true, then CSPs provide one of the largest known subsets of NP which avoids problems that are neither polynomial time solvable nor NP-complete, whose existence was demonstrated by Ladner. Dichotomy results are known for CSPs where the domain of values is of size 2 or 3, but the general case is still open.

Most classes of CSPs that are known to be tractable are those where the hypergraph of constraints has bounded treewidth (and there are no restrictions on the set of constraint relations), or where the constraints have arbitrary form but there exist essentially non-unary polymorphisms of the set of constraint relations.