from ${\mathbf{A}}$ to ${\mathbf{B}}$, then the mapping sending each $a \in A$ to the set $\{ h(a) \}$ is a homomorphism from ${\mathbf{A}}$ to ${\wp}({\mathbf{B}})$.

\[thm:ac-solves\] Let ${\mathbf{B}}$ be a structure. Arc consistency solves ${{\mathsf{CSP}}}({\mathbf{B}})$ if and only if there is a homomorphism ${\wp}({\mathbf{B}}) \rightarrow {\mathbf{B}}$.

Look-Ahead Arc Consistency {#ss:laac}
--------------------------

We now present the look-ahead arc consistency algorithm. It attempts to construct a satisfying assignment by setting one variable at a time, using arc consistency as a filter to find a suitable value for each variable.

[ **Look-Ahead Arc Consistency**]{}\

------------------------------------------------------------------------

Look-ahead arc consistency was introduced and studied by Chen and Dalmau [@SLAAC], and the theorem that follows is due to them. This algorithm can be viewed as a generalization of an algorithm for SAT studied by Del Val [@delval].

\[def:laac-solves\] Let ${\mathbf{B}}$ be a structure. We say that look-ahead arc consistency *solves* ${{\mathsf{CSP}}}({\mathbf{B}})$ if for all structures ${\mathbf{A}}$, the following holds: if there exists a homomorphism ${\mathbf{A}}\rightarrow {\mathbf{B}}$, then the look-ahead arc consistency algorithm, given $({\mathbf{A}}, {\mathbf{B}})$, outputs such a homomorphism.

\[thm:laac-solves\] Let ${\mathbf{B}}$ be a structure. Look-ahead arc consistency solves ${{\mathsf{CSP}}}({\mathbf{B}})$ if and only if there is a homomorphism $l: {\wp}({\mathbf{B}}) \times {\mathbf{B}}\rightarrow {\mathbf{B}}$ such that $l( 