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 constraint satisfaction problems:
Algorithms used for solving constraint satisfaction problems include the AC-3 algorithm, Backtracking, and the min-conflicts algorithm.
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.
See also
- Constraint satisfaction
- Declarative programming
- Constraint programming
- Distributed Constraint Satisfaction Problem (DisCSP)
External links
- Tsang, Edward (1993). Foundations of Constraint Satisfaction. Academic Press. ISBN 0-12-701610-4
- Dechter, Rina (2003). Constraint processing. Morgan Kaufmann. ISBN 1-55860-890-7
- Apt, Krzysztof (2003). Principles of constraint programming. Cambridge University Press. ISBN 0-521-82583-0
- Tomás Feder, Constraint satisfaction: a personal perspective, manuscript.
- Constraints archive
- Forced Satisfiable CSP Benchmarks of Model RB
- Benchmarks -- XML representation of CSP instances
