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:
“America is the world’s living myth. There’s no sense of wrong when you kill an American or blame America for some local disaster. This is our function, to be character types, to embody recurring themes that people can use to comfort themselves, justify themselves and so on. We’re here to accommodate. Whatever people need, we provide. A myth is a useful thing.”
—Don Delillo (b. 1926)
“People who love only once in their lives are ... shallow people. What they call their loyalty, and their fidelity, I call either the lethargy of custom or their lack of imagination. Faithfulness is to the emotional life what consistency is to the life of the intellect—simply a confession of failures.”
—Oscar Wilde (1854–1900)