Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Local consistency
open-in-new
<p>In <a href="/facts/Constraint_satisfaction/PXI74p1T">constraint satisfaction</a>, local consistency conditions are properties of <a href="/facts/Constraint_satisfaction_problem/oKCeIV2L">constraint satisfaction problems</a> related to the <a href="/facts/Consistency/IHkdnA9M">consistency</a> of subsets of variables or constraints. They can be used to reduce the search space and make the problem easier to solve. Various kinds of local consistency conditions are leveraged, including node consistency, arc consistency, and path consistency. </p><p>Every local consistency condition can be enforced by a transformation that changes the problem without changing its solutions; such a transformation is called constraint propagation. Constraint propagation works by reducing domains of variables, strengthening constraints, or creating new constraints. This leads to a reduction of the search space, making the problem easier to solve by some algorithms. Constraint propagation can also be used as an unsatisfiability checker, incomplete in general but complete in some particular cases. </p><p>Local consistency conditions can be grouped into various classes. The original local consistency conditions require that every consistent partial assignment (of a particular kind) can be consistently extended to another variable. Directional consistency only requires this condition to be satisfied when the other variable is greater than the ones in the assignment, according to a given order. Relational consistency includes extensions to more than one variable, but this extension is only required to satisfy a given constraint or set of constraints. </p>