= 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+ed^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> costs
$$
\boxed{O\bigl((vd+1)(ed^2+v)\bigr).}
$$
If empty-domain detection is maintained during revisions rather than rescanned, the familiar comparison is $O(ved^3)$ versus $O(ed^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>.
Back to article page
