Examples of problems that can be modelled as a constraint satisfaction problem:
Formally, a constraint satisfaction problem is defined a triple , where is a set of variables, is a domain of values, and is a set of constraints. Every constraint is in turn a pair , where is a tuple of variables and is a set of tuples of values; all these tuples having the same number of elements; as a result is a relation. An evaluation of the variables is a function from variables to domains, . Such an evaluation satisfies a constraint if . A solution is an evaluation that satisfies all constraints.
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.
Agency Reviews Patent Application Approval Request for "Constraint Satisfaction Problem Solving Using Constraint Semantics"
May 30, 2013; By a News Reporter-Staff News Editor at Politics & Government Week -- International Business Machines Corporation has been issued...