From Russell-Norvig:

A CSP is strongly k-consistent if it is k-consistent and is also (k − 1)-consistent, (k − 2)-consistent, . . . all the way down to 1-consistent.

How can a CSP be k-consistent without being (k - 1)-consistent? I can't think of any counter example for this case. Any help would be appreciated.


Define P as a CSP where X, Y are the variables, domain of both is {1,2,3,4} and conditions in normal form are:

  1. node-condition X<4
  2. arc-condition X=Y

P is 2-consistent (arc consistent) because for any X value it is possible to find a Y value that fulfills the arc-condition X=Y.

However, P is not 1-consistent (node-consistent) because exist a X value (X=4) that can not fulfill the node condition x<4.

For these reasons, this problem is 2-consistent but not strongly 2-consistent.

Obviously, it is straightforward to convert this example in a strongly 2-consistent problem, just reducing the domain to {1,2,3}.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.