---
title: "Why AC-3 is Almost Always Better than AC4 for Establishing Arc Consistency in CSPs"
authors:
  - "Richard J. Wallace"
doi: ""
url: "https://ijcai.org/proceedings/1993/34"
pdf: "https://ijcai.org/proceedings/1993/0034.pdf"
venue: "Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence"
year: 1993
pages: "239-246"
track: "Constraint Satisfaction Problems"
keywords:
---

# Why AC-3 is Almost Always Better than AC4 for Establishing Arc Consistency in CSPs

Richard J. Wallace

*Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence*, pages 239-246.

## 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, AC3 was found to be much more efficient th~m AC-4, for CSPs with a variety of features. (Variable pairs were in lexical order, ~md 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 nmge of constraint satisfiabilities ~md for the unlikelihood of conditions leading to worst-case perfonmmce. The efficiency of AC-4 is affected by the order of variable testing in Phase 1 ('setting up' phase); perform~mce 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 smne orderings, it still outperforms AC-4 in most cases.