Such a decomposition of the Permutation **constraint obviously does not hinder**
propagation. However, decomposition of AllDifferent into a Range **constraint does.**
This example illustrates that, whilst many global constraints can be expressed in terms of Range and Roots, there are some global constraints like AllDifferent **for which** it is worth developing specialised propagation algorithms. Nevertheless, Range and Roots **provide a means of propagation for such constraints in the absence of specialised**
algorithms. They can also enhance the existing propagators. For instance, HC on the Range decomposition is incomparable to AC on the decomposition of **AllDifferent**
which uses a clique of binary inequality constraints. Thus, we may be able to obtain more pruning by using both decompositions.

Theorem 8 (1) GAC on Permutation **is equivalent to HC on the decomposition with**
Range. (2) GAC on AllDifferent **is stronger than HC on the decomposition with** Range. (3) AC on the decomposition of AllDifferent **into binary inequalities is** incomparable to HC on the decomposition with **Range**.

Proof: (1) Permutation can be encoded as a single Range**. Moreover, since** R is fixed, HC is equivalent to AC. (2) Consider X1, X2 ∈ {1, 2}, X3 ∈ {1, 2, 3, 4}**, and**
{1, 2} ⊆ T ⊆ {1, 2, 3, 4}. Then Range([X1, X2, X3], {1, 2, 3}, T ) and |T | **= 3 are both** HC, but AllDifferent([X1, X2, X3]) is not GAC. (3) Consider X1, X2 ∈ {1, 2}, X3 ∈
{1, 2, 3}, and T = {1, 2, 3}. Then X1 6= X2, X1 6= X3 and X2 6= X3 **are AC but**
Range([X1, X2, X3], {1, 2, 3}, T ) is not HC. Consider X1, X2 ∈ {1, 2, 3, 4}, X3 ∈ {2}, and {2} ⊆ T ⊆ {1, 2, 3, 4}. Then Range([X1, X2, X3], {1, 2, 3}, T ) and |T | **= 3 are HC.**
But X1 6= X3 and X2 6= X3 **are not AC.** ✷

## 6.1.2 Disjoint

We may require that two sequences of variables be disjoint (i.e. have **no value in common).** For instance, two sequences of tasks sharing the same resource **might be required to**
be disjoint in time. The Disjoint([X1, .., Xn], [Y1, .., Ym**]) constraint introduced in [2]**
ensures Xi 6= Yj for any i and j**. We prove here that we cannot expect to enforce GAC**
on such a constraint as it is NP-hard to do so in general.

Theorem 9 Enforcing GAC on Disjoint **is NP-hard.**
Proof: We reduce 3-SAT to the problem of deciding if a Disjoint **constraint has any**
satisfying assignment. Finding support is therefore NP-hard. Consider a formula ϕ with n variables and m clauses. For each Boolean variable x, we let Xx ∈ {x, ¬x} and Yj ∈ {x, ¬y, z} where the jth clause in ϕ is x ∨ ¬y ∨ z. If ϕ **has a model then the**
Disjoint constraint has a satisfying assignment in which the Xx **take the literals false**
in this model. ✷
One way to propagate a Disjoint constraint is to decompose it into two **Range**
constraints:
Disjoint([X1, .., Xn], [Y1, .., Ym**]) iff**
Range([X1, .., Xn], {1, .., n}, S) ∧ Range([Y1, .., Ym], {1, .., m}, T ) ∧ S ∩ T = {}