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 fixed level of local consistency is sufficient to ensure global consistency. In this paper we describe a simple algebraic property which characterises 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.