New tractable constraint classes from old
David A. Cohen, Peter Jeavons, Richard Gault · Morgan Kaufmann Publishers Inc. eBooks · 2003
Many applications in AI involve searching over a very large possibility space. Constraint satisfaction is a general problem-solving paradigm that expresses some of these search problems in a natural way.The constraint-satisfaction paradigm consists of defining a problem in terms of variables that need to be assigned suitable values. Certain subsets of these variables are then constrained by restricting the simultaneous values they may be assigned.In general, the constraint-satisfaction problem is NP-hard but there are well-known restrictions to the hypergraph of constraint interactions (structure) or to the allowable relations of constraint restrictions (language) that make the problem tractable (solvable in polynomial time). The trade-off here is expressiveness for tractability.In this chapter, we introduce the constraint-satisfaction paradigm and briefly describe expressiveness and tractability. We then introduce an algebraic framework for describing language-based tractability and discuss some of the known results. Lastly, we derive a general technique for developing new, more expressive, tractable constraint languages from existing examples.