might introduce new constraints. When two variables are not related by a binary constraint, they are virtually related by the constraint allowing any pair of values. However, some pair of values might be removed by constraint propagation. The resulting constraint is no longer satisfied by all pairs of values. Therefore, it is no longer a virtual, trivial constraint. The name "path consistency" derives from the original definition, which involved a pair of variables and a path between them, rather than a pair and a single variable. While the two definitions are different for a single pair of variables, they are equivalent when referring to the whole problem. Generalizations Arc and path consistency can be generalized to non-binary constraints using tuples of variables instead of a single one or a pair. A tuple of variables is -consistent with another variable if every consistent evaluation of the variables can be extended with a value of the other variable while preserving consistency. This definition extends to whole problems in the obvious way. Strong -consistency is -consistency for all . The particular case of 2-consistency coincides with arc consistency (all problems are assumed node-consistent in this article). On the other hand, 3-consistency coincides with path consistency only if all constraints are binary, because path consistency does not involve ternary constraints while 3-consistency does. Another way of generalizing arc consistency is hyper-arc consistency or generalized arc consistency, which requires extendibility of a single variable in order to satisfy a constraint. Namely, a variable is hyper-arc consistent with a constraint if every value of the variable can be extended to the other variables of the constraint in such a way the constraint is satisfied. Consistency and satisfiability Constraint propagation (enforcing a form of local consistency) might produce an empty domain or an unsatisfiable constraint. In this case, the problem has no solution. The converse is not true in general: an inconsistent instance may be arc consistent or path consistent while having no empty domain or unsatisfiable constraint. Indeed, local consistency is only relative to the consistency of groups of variables. For example, arc consistency guarantees that every consistent evaluation of a variable can be consistently extended to another variable. However, when a single value of a variable is extended to two other variables, there is no guarantee that these two values are consistent with each other. For example, may be consistent with and with , but