Functional Elimination and 0/1/All Constraints

Abstract

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. 1. Introduction Constraint Satisfaction Problem(s) (CSP) are known to be NP-complete in general (Mackworth 1977). There are two approaches for attacking the computational intractability. One way is to identify those tractable class of problems by suitable restrictions so that it can be solved in polynomial time. A restriction is on the topologi...