Uses of Local Consistency
All forms of local consistency can be enforced by constraint propagation, which may reduce the domains of variables and the sets of assignments satisfying a constraint and may introduce new constraints. Whenever constraint propagation produces an empty domain or an unsatisfiable constraint, the original problem is unsatisfiable. Therefore, all forms of local consistency can be used as approximations of satisfiability. More precisely, they can be used as incomplete unsatisfiability algorithms, as they can prove that a problem is unsatisfiable, but are in general unable to prove that a problem is satisfiable. Such approximated algorithms can be used by search algorithms (backtracking, backjumping, local search, etc.) as heuristics for telling whether a partial solution can be extended to satisfy all constraints without further analyzing it.
Even if constraint propagation does not produce an empty domain or an unsatisfiable constraint, it may nevertheless reduce the domains or strengthen the constraints. If this is the case, the search space of the problem is reduced, thus reducing the amount of search needed to solve the problem.
Local consistency proves satisfiability in some restricted cases (see Complexity of constraint satisfaction#Restrictions). This is the case for some special kind of problems and/or for some kinds of local consistency. For example, enforcing arc consistency on binary acyclic problems allows for telling whether the problem is satisfiable. Enforcing strong directional -consistency allows telling the satisfiability of problems that have induced width according to the same order. Adaptive directional consistency allows telling the satisfiability of an arbitrary problem.
Read more about this topic: Local Consistency
Famous quotes containing the words local and/or consistency:
“The poet’s eye, in a fine frenzy rolling,
Doth glance from heaven to earth, from earth to heaven;
And as imagination bodies forth
The forms of things unknown, the poet’s pen
Turns them to shapes, and gives to airy nothing
A local habitation and a name.”
—William Shakespeare (1564–1616)
“All religions have honored the beggar. For he proves that in a matter at the same time as prosaic and holy, banal and regenerative as the giving of alms, intellect and morality, consistency and principles are miserably inadequate.”
—Walter Benjamin (1892–1940)