Why AC-3 is almost always better than AC-4 for establishing arc consistency in CSPs

Abstract

On the basis of its optimal asymptotic time complexity, AC-4 is often considered the best algorithm for establishing arc consistency in constraint satisfaction problems (CSPs). In the present work, AC-3 was found to be much more efficient than AC-4, for CSPs with a variety of features. (Variable pairs were in lexical order, and in AC-3 they were added to the end of the list of pairs.) This is supported by arguments for the superiority of AC-3 over most of the range of constraint satisfiabilities and for the unlikelihood of conditions leading to worst-case performance. The efficiency of AC-4 is affected by the order of variable testing in Phase 1 ('setting up ' phase); performance in this phase can thus be enhanced, and this establishes initial conditions for Phase 2 that improve its performance. But, since AC-3 is improved by the same orderings, it still outperforms AC-4 in most cases. 1