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

Interpret MyAC as doing at least one initial sweep, then repeating while the preceding sweep deleted a value. Its loop guard otherwise has no initialized truth condition. Both procedures apply the same support-based deletion rule, so both preserve every solution and terminate because finite constraint domains only shrink. Both return false on a detected empty constraint domain; neither successful return establishes satisfiability.

If a sweep changes no constraint domain, every directed arc has been revised against unchanged constraint domains, so all arcs satisfy arc consistency. Conversely, AC-3 places every potentially affected incoming arc back on its work list after a deletion. Its empty work list therefore also establishes arc consistency. When both run to successful completion, they compute the same arc-consistency closure, independently of revision order. To see maximality, any subdomains of the initial constraint domains that satisfy arc consistency survive every revision: each of their values retains a support inside those subdomains. Thus neither procedure can delete a value belonging to any such fixed point. Early failure may leave different intermediate constraint domains, but both failures correctly prove impossibility.

Their scheduling costs differ. AC-3 directs work toward arcs that may have lost supports, with standard time complexity $O(v+e{d}^3)$. The full-sweep arc consistency method revisits all $2e$ arcs after even one remote change. There are at most $vd$ value deletions, so at most $vd+1$ sweeps; a direct implementation including a scan for empty constraint domains costsIf empty-domain detection is maintained during revisions rather than rescanned, the familiar comparison is $O(ve{d}^3)$ versus $O(e{d}^3)$, apart from initialization. These are upper bounds, not exact costs on every input.

In practice MyAC is simple and may have low overhead or benefit from a fortunate sweep order. It can also waste many scans after changes propagate slowly opposite to that order. AC-3 incurs work-list bookkeeping but normally avoids those unrelated revisions. Both inherit the inability of arc consistency to decide arbitrary constraint satisfaction problems.