polynomial sized decomposition of NVALUE which achieves domain consistency [6]. Nevertheless, we show that decomposition can simulate the polynomial time algorithm for enforcing bound consistency on NVALUE but with a significant space complexity.

We also prove, for the first time, that range consistency on NVALUE can be enforced in the same worst case time complexity as bound consistency. This contrasts with the ALL-DIFFERENT constraint where range consistency takes O(n 2) time [2] but bound consistency takes just O(n log n) time [3].

The main value of these decompositions is theoretical as their space complexity is equal to their worst case time complexity. When domains are large, this space complexity may be prohibitive. In the conclusion, we argue why it appears somewhat inevitable that the space complexity is equal to the worst case time complexity. These results suggest new insight into what is and isn't a global constraint: a global constraint either provides more pruning than any polynomial sized decomposition or provides the same pruning but with lower space complexity. There are several other theoretical reasons why the decompositions studied here are interesting. First, it is technically interesting that a complex propagation algorithm like the bound consistency propagator for NVALUE can be simulated by a simple decomposition. Second, these decompositions can be readily encoded as linear inequalities and used in linear programs. In fact, we will report experiments using both constraint and integer linear programming with these decompositions. Since global constraints are one of the key differentiators between constraint and integer programming, these decompositions provide us with another tool to explore the interface between constraint and integer programming. Third, the decompositions give insights into how we might add nogood learning to a NVALUE propagator.

## 2 Background

A constraint satisfaction problem (CSP) consists of a set of variables, each with a finite domain of values, and a set of constraints. We use capitals for variables and lower case for values. We assume values are taken from the set 1 to d. We write dom(Xi) for the domain of possible values for Xi, min(Xi) for the smallest value in dom(Xi),
max(Xi) for the greatest, and **range**(Xi) for the interval [min(Xi)**, max**(Xi)]. Constraint solvers typically use backtracking search to explore the space of partial assignments. After each assignment, propagation algorithms prune the search space by enforcing local consistency properties like domain, range or bound consistency. A constraint is *domain consistent* (DC) iff when a variable is assigned any of the values in its domain, there exist compatible values in the domains of all the other variables of the constraint. Such an assignment is called a *support*. A CSP is domain consistent iff every constraint is domain consistent. A constraint is *disentailed* iff there is no possible support. A propagator which enforces domain consistency will detect disentailment, but a propagator that detects just disentailment will not enforce domain consistency. A constraint is *range consistent* (RC) iff, when a variable is assigned any of the values in its domain, there exist compatible values between the minimum and maximum domain value for all the other variables of the constraint. Such an assignment is called a *bound* support. A constraint is *bound consistent* (BC) iff the minimum and maximum value of every variable of the constraint belong to a bound support. A CSP is bound con-