CLOSURE-PROPERTIES OF CONSTRAINTS

Many combinatorial search problems can be expressed as ''constraint sa tisfaction problems'' and this class of problems is known to be NP-com plete in general. In this paper, we investigate the subclasses that ar ise from restricting the possible constraint types. We first show that any set of constraints that does not give rise to an NP-complete clas s of problems must satisfy a certain type of algebraic closure conditi on. We then investigate all the different possible forms of this algeb raic closure property, and establish which of these are sufficient to ensure tractability. As examples, we show that all known classes of tr actable constraints over finite domains can be characterized by such a n algebraic closure property. Finally, we describe a simple computatio nal procedure that can be used to determine the closure properties of a given set of constraints. This procedure involves solving a particul ar constraint satisfaction problem, which we call an ''indicator probl em.''