CONSTRAINTS, CONSISTENCY AND CLOSURE

Although the constraint satisfaction problem is NP-complete in general , a number of constraint classes have been identified for which some f ixed level of local consistency is sufficient to ensure global consist ency. In this paper we describe a simple algebraic property which char acterises all possible constraint types for which strong k-consistency is sufficient to ensure global consistency, for each k > 2. We give a number of examples to illustrate the application of this result. (C) 1998 Elsevier Science B.V. All rights reserved.