Proof: We reduce 3-SAT to the problem of deciding if a Uses **constraint has a solution.**
Finding support is therefore NP-hard. Consider a formula ϕ with n **Boolean variables**
and m clauses. For each Boolean variable x, we introduce a variable Xx ∈ {x, −x}**. For** each clause cj = x ∨ ¬y ∨ z, we introduce Yj ∈ {x, −y, z}. Then ϕ **has a model iff the**
Uses constraint has a satisfying assignment, and x **is true iff** Xx = x. ✷
One way to propagate a Uses constraint is to decompose it using Range **constraints:**
Uses([X1, .., Xn], [Y1, .., Ym**]) iff**
Range([X1, .., Xn], {1, .., n}, T ) ∧
Range([Y1, .., Ym], {1, .., m}, T ′) ∧ T
′ ⊆ T
Enforcing HC on this decomposition is polynomial. Not surprisingly, this **hinders**
propagation (otherwise we would have a polynomial algorithm for a NP-hard problem).

Theorem 13 GAC on Uses **is stronger than HC on the decomposition.**
Proof: Consider X1 ∈ {1, 2, 3, 4}, X2 ∈ {1, 2, 3, 5}, X3, X4 ∈ {4, 5, 6}, Y1 ∈ {1, 2},
Y2 ∈ {1, 3}, and Y3 ∈ {2, 3}. The decomposition is HC while GAC on Uses **prunes 4**
from the domain of X1 **and 5 from the domain of** X2. ✷
Thus, decomposition is a simple method to obtain a polynomial propagation algorithm.

## 6.2 Applications Of Roots **Constraint**

Range **constraints are often useful to specify constraints on the values used by a sequence** of variables. Roots **constraint, on the other hand, are useful to specify constraints on**
the variables taking particular values.

## 6.2.1 Global Cardinality

The global cardinality constraint introduced in [26] constrains the number of times values are used. We consider a generalization in which the number of occurrences of a value may itself be an integer variable. More precisely, Gcc([X1, .., Xn], [d1, .., dm], [O1**, .., O**m])
holds iff |{i | Xi = dj}| = Oj for all j. Such a Gcc **constraint can be decomposed into a**
set of Roots **constraints:**
Gcc([X1, .., Xn], [d1, .., dm], [O1, .., Om**]) iff**
∀i . Roots([X1, .., Xn], Si, {di}) ∧ |Si| = Oi Enforcing HC on these Roots constraints is polynomial since the sets {di} **are ground**
(See Theorem 5). Enforcing GAC on a generalised Gcc **constraint is NP-hard, but we**
can enforce GAC on the Xi and BC on the Oj **in polynomial time using a specialised**
algorithm [24]. This is more than is achieved by the decomposition.

Theorem 14 GAC on the Xi and BC on the Oj of a Gcc **constraint is stronger than**
HC on the decomposition using Roots **constraints.**