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.