Arc consistency

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Arc consistency
Are two variables (u,v) arc consistent, if $C_{uv} \notin C$ and ($d_u = \emptyset$ or $d_v = \emptyset$)?


Yes, but only because the first condition C_{uv} \notin C is already sufficient. The second conjunct is not sufficient,
because d_v = \emptyset does not guarantee arc consistency.d_u = \emptyset is sufficient, since quantifying over an empty set is always true. Also note that d_v = emptyset conditions aren’t really relevant for arc consistency, because any algorithm should detect empty domains.


OBJECTION. Arc consistency is not symmetric - u can be arc consistent relative to v, v can be arc consistent relative to u, or both, or neither. Just to be clear :wink:

So the definition of u being arc consistent relative to v is that „For all x\in d_u, there exists some y \in d_v such that…“. A statement of the form „for all x\in S“ is always true if S is the empty set. So if d_u is empty, then u is arc consistent relative to every other variable.
A statement of the form „there exists some x\in S…“ is always false if S is the empty set. So if d_u is not empty, but d_v is, then u is not arc consistent relative to v.

Now, if neither d_u nor d_v are empty, but C_{uv} not in C, then there is no constraint between u and v, so so any pair of values from d_u and d_v is (in principle, barring other constraints) valid, so u is arc consistent relative to v and v is arc consistent relative to u :slight_smile: