Constraint Satisfaction Problems
by
Roger D Maddux
Department of Mathematics, Iowa State University, Ames, USA

A constraint satisfaction problem (CSP) is specified by a collection of (usually binary) constraints on the variables; the problem is to find values for the variables that satisfy the constraints. Planning and scheduling are common sources for such problems. Many problems are NP-hard, while others have less severe complexity bounds. Binary CSPs can be formulated in terms of relation algebras. For computational purposes the standard formulation is restricted to finite domains, while the relation-algebraic formulation is convenient for infinite domains. Specific interesting algebras arise from applications, such as the Point Algebra, J. Allen's Interval Algebra, the Hard Algebra, the Containment Algebra, and the various Compass Algebras for reasoning about spatial relationships.

Date received: January 3, 2001