On the Consistency of General Constraint-Satisfaction Problems

Philippe Jégou

The problem of checking for consistency of Constraint-Satisfaction Problems (CSPs) is a fundamental problem in the field of constraint-based reasoning. Moreover, it is a hard problem since satisfiability of CSPs belongs to the class of NP-complete problems. So, in (Freuder 1982), Freuder gave theoretical results concerning consistency of binary CSPs (two variables per constraints). In this paper, we proposed an extension to these results to general CSP (n-ary constraints). On one hand, we define a partial consistency well adjusted to general CSPs called hyper-k-consistency. On the other hand, we proposed a measure of the connectivity of hypergraphs called width of hypergraphs. Using width of hypergraphs and hyper-k-consistency, we derive a theorem defining a sufficient condition for consistency of general CSPs.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.