= Solution
\b[The first assertion is true.] Each deletion removes a value with no support in an adjacent <constraint domain>. If a complete solution still used that value, the solution’s neighboring value would supply exactly such a support, a contradiction. By <mathematical induction>, <AC-3> never deletes a value used by an original solution. An empty <constraint domain> therefore proves that no solution exists.
\b[The second assertion is false.] Take three <Boolean variables> $X,Y,Z$ with <constraint domains> $\{0,1\}$ and the <binary constraints> $X\ne Y$, $Y\ne Z$, $Z\ne X$. Every value has the opposite value as support across each <edge>, so <AC-3> deletes nothing and returns true. Yet $X\ne Y$ and $Y\ne Z$ imply $X=Z$, contradicting $Z\ne X$. <Arc consistency> checks local support, not compatibility of all supports in one complete assignment.
\Image[/past-exam-of-the-computer-science-course-of-the-university-of-oxford/2022/artificial-intelligence-arc-consistency-triangle.png]
{title=Every value has pairwise support, but following the three inequality constraints makes a complete assignment impossible}
\b[The third assertion is true under the usual explicit-input, constant-cost constraint-checking model.] With $v$ variables, $e$ constrained pairs and maximum <constraint domain> size $d$, <AC-3> has <time complexity> $O(v+ed^3)$ in <Big O notation>. A revision costs $O(d^2)$; each deletion can re-enqueue incoming arcs, and each <constraint domain> loses at most $d$ values, giving $O(ed)$ revisions including the initial arcs. For two-valued <constraint domains>, $d\le2$, so this is \b[$O(v+e)$], linear in the explicit input size. This uses fixed-size relations, or already combined constant-time tests per pair. “Binary” normally describes constraint arity, not two-valued <constraint domains>; the latter restriction is the extra hypothesis needed here. As usual, initially empty <constraint domains> should be rejected before entering the algorithm, including isolated variables.
Back to article page
