An important concept in CSPs is the concept of local consistency. Local consistencies are properties that can be applied in a CSP, using (typically) polynomial algorithms, to remove inconsistent values either prior to or during search. Arc consistency is the most commonly used local consistency property in the existing constraint programming engines. We now give a definition of arc consistency.

The usefulness of AC processing was recognized early, and as a result, various AC algorithms for binary constraints have been proposed in the literature (e.g. AC-3 in mac77, AC-4 in mh86, AC-5 in vhdt92, AC-7 in bfr95, AC-2001 in br01, AC3.1 in yap01). Some of them have been extended to the non-binary case (e.g. GAC-4 in mm88, GAC-Schema in br97, GAC-2001 in br01). AC can be enforced on a binary CSP with optimal worst-case time complexity. The worst-case complexity of enforcing GAC on a non-binary CSP is [Bessière RéginBessière Régin1996a].

In this paper we use algorithms AC-2001 and GAC-2001 for theoretical and empirical comparisons with specialized algorithms for the encodings. This is not restrictive, in the sense that any generic AC (and GAC) algorithm can be used instead.

Following Debruyne & Bessiére db97, we call a local
consistency property *stronger* than iff for any
problem enforcing deletes at least the same values as , and
*strictly stronger* iff it is stronger and there is at least
one problem where deletes more values than . We call
*equivalent* to iff they delete the same values for all
problems. Similarly, we call a search algorithm stronger than
a search algorithm iff for every problem visits at most
the same search tree nodes as , and strictly stronger iff it is
stronger and there is at least one problem where visits less
nodes than . is equivalent to iff they visit the same
nodes for all problems.

Following Bacchus et al. bcvbw02, the *asymptotic
cost* (or just cost hereafter) of a search algorithm is
determined by the worst-case number of nodes that the algorithm
has to visit to solve the CSP, and the worst-case time complexity
of the algorithm at each node^{1}. As in the paper by Bacchus et al.
bcvbw02, we use this measure to set asymptotic bounds
in the relative performance of various algorithms. For example, if
two algorithms and always visit the same nodes and
enforces a property at each node with exponentially higher
complexity than the property enforced by , then we say that
*algorithm can have an exponentially greater cost than
algorithm *.

Nikolaos Samaras 2005-11-09