Hardness & Local Consistency

• An n-variable CSP problem is said to be k-consistent iff every consistent assignment for (k-1) of the n variables can be extended to include any k-th variable

  • Directional consistency: Assignment to first k-1 variables can be extended to the k-th variable
  • Strongly k-consistent if it is j-consistent for all j from 1 to k

• Higher the level of (strong) consistency of problem, the lesser the amount of backtracking required to solve the problem

  • A CSP with strong n-consistency can be solved without any backtracking

• We can improve the level of consistency of a problem by explicating implicit constraints

  • Enforcing k-consistency is of O(nk) complexity
    • Break-even seems to be around k=2
    • Use of directional and partial consistency enforcement techniques

Previous slide

Next slide

Back to first slide

View graphic version