sistent iff every constraint is bound consistent. We compute the total amortized cost of enforcing a local consistency down an entire branch of the search tree. This captures the incremental cost of propagation. Finally, we will assume that a propagator is invoked at most once for each domain change and that the solver uses an optimal propagator to enforce BC on sum and channeling constraints. Such assumptions hold for modern solvers like Gecode and Ilog Solver. However, we make no assumption about the order of invocation of the constraints in a decomposition. The upper bounds we give hold regardless of the order in which constraints are processed.

A *global constraint* is one in which the arity of the constraint n is a parameter. A
decomposition of a global constraint is a CSP involving the n variables of the global constraint (and possibly others), involving only constraints with fixed arity (no global constraint) or constraints that are themselves decomposable, such that the size of the CSP is polynomial in the sum of the sizes of the domains of the n original variables, and such that the projection of its solutions on those n variables corresponds to the solutions of the global constraint. A useful notion is algorithmic globality [4]. Informally, given a local consistency property, a global constraint is algorithmically global if there is no decomposition on which this local consistency is achieved in the same time and space complexity. We suggest here two refinements of this notion of algorithmic globality. First, we will separate the space and time complexity. That is, given a local consistency property, a global constraint is algorithmically global with respect to time (space) if there is no decomposition on which this local consistency is achieved in the same time (space) complexity. Second, unlike [4], we consider decompositions that may introduce new variables. Our results will show that, when we introduce new variables, NVALUE
is not algorithmically global with respect to time but is global with respect to space.

## 3 Nvalue Constraint

Pachet and Roy first proposed the NVALUE constraint [8]. Formally NVALUE([X1, . . . , Xn], N) ensures that N = |{Xi| 1 ≤ i ≤ n}|. This generalizes several other global constraints including ALL-DIFFERENT (which ensures that the number of values taken by a set of variables equals the cardinality of the set) and NOT-ALL-EQUAL (which ensures a set of variables take more than one value).

Enforcing domain consistency on the NVALUE constraint is NP-hard (Theorem 3 in
[7]) even when N is fixed (Theorem 2 in [9]). In fact, just computing the lower bound on N is NP-hard (Theorem 3 in [10]). In addition, enforcing domain consistency on the NVALUE constraint is not fixed parameter tractable since it is W[2]-complete [11].

However, several polynomial propagation algorithms have been proposed that achieve bound consistency and some closely related levels of local consistency [12, 9, 13].

## 3.1 Simple Decomposition

Global constraints can often be decomposed into simpler, more primitive and small arity constraints. For example, the ALL-DIFFERENT constraint can be decomposed into a quadratic number of binary inequalities. However, such decomposition often hinders propagation and can have a significant impact on the solver's ability to find solutions