Functional Elimination and 0/1/All Constraints

Proceedings of the AAAI Conference on Artificial Intelligence, 16

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 16

Constraint Satisfaction Problems

We present new complexity results on the class of 0/1/All constraints. The central idea involves functional elimination, a general method of elimination whose focus is on the subclass of functional constraints. One result is that for the subclass of All constraints, strong n-consistency and minimality is achievable in O(en) time, where e, n are the number of constraints and variables. The main result is that we can solve 0/1/All constraints in O(e(d+n)) time, where d is the domain size. This is an improvement over known results, which are O(ed(d+n)). Furthermore, our algorithm also achieves strong n-consistency and minimality.