${\mathbf{B}}$ such that the algorithm solves ${{\mathsf{CSP}}}({\mathbf{B}})$. These three algorithms give one-sided consistency checks: each either correctly rejects an instance as unsatisfiable or outputs “?”, which can be interpreted as a report that it is unknown whether or not the instance is satisfiable. The other algorithm, look-ahead arc consistency, has a somewhat different character. It attempts to build a satisfying assignment one variable at a time, using arc consistency as a filtering criterion; it either returns a satisfying assignment, or outputs “?”.

Throughout this section and in later sections, we will make use of a structure ${\wp}({\mathbf{B}})$ that is defined for every structure ${\mathbf{B}}$, as follows [@FederVardi; @DalmauPearson]. For a structure ${\mathbf{B}}$ (over $\sigma$), we define ${\wp}({\mathbf{B}})$ to be the structure with universe ${\wp}(B) \setminus \{ \emptyset \}$ and where, for every symbol $R \in \sigma$ of arity $k$, $R^{{\wp}({\mathbf{B}})} = \{ (\pi_1 S, \ldots, \pi_k S) ~|~ S \subseteq R^{{\mathbf{B}}}, S \neq \emptyset \}$. Here, ${\wp}(B)$ denotes the power set of the set $B$.

Arc Consistency {#ss:ac}
---------------

We now present the arc consistency algorithm. The main idea of the algorithm is to associate to each element $a \in A$ a set $S_a$ of values which, throughout the execution 