Past exam of the computer science course of the University of Oxford / 2022 / Artificial intelligence / 3 / a / Solution

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.

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.

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+e{d}^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\le 2$, so this is $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.