
| Rel of M C   | Rel of RCC   |
|--------------|--------------|
| CG           | EQ           |
| CGPP         | PP           |
| CGPP         | P-           |
| CNO          | PO           |

Table The basic relations of MC
and their counterparts in RCC
in the special map ping  Ω
roto translate a by T so that T a  PP b  Finally two regions are in a CNO relation iff they can only be in a PO relation or disjoint The correspondence of Table is called Ω and a Network of Constraints G on MC
translated in RCC    by it is denoted by Ω G    The networks which are labelled on all edges by basic relations of MC are henceforth called scenarios of MC
Consider a consistent scenario S of MC      Applying the composition tables of MC    and we clearly derive that the scenario of RCC Ω S  is consistent  when the scenario RCC
of MC   does so  The consequence of above reasoning is the next lemma Lemma 1 If a scenario on MC-4 is consistent, then Ω G is consistent.

Ladkin and Maddux proved that a network of constraints is consistent iffit has a consistent scenario  Therefore  an immediate consequence of Lemma   is that if a network of constraints G on MC is consistent then Ω G is consistent We are now able to prove a first theorem

## Theorem 1 Msat Mc

is NP-hard.

## Proof

By the observation about existence of consistent scenarios in a Constraint Algebra due we obtain a polynomial reduction of RSAT RCC
to Mackworth and Freuder to MSAT MC
It suffices to note that if we can solve MSAT then we can solve RCC problems obtained by the Ω translation as well Now the problems mapped from MC into RCC by means of Ω can be trivially inverted by Ω − ¹  since Ω is trivially one to one  This means that each problem in the set of relations obtained in RCC    by Ω corresponds to a problem in MC
and vice versa The set of relations of RCC translated by Ω contains {PP, PP- 1 } and PO Nebel and Renz proved that each set of relations of RCC containing these two relations is intractable  Therefore the set Ω MC -    is intractable This proves that if we are able to solve a problem in MC
we can solve a problem of a subset of RCC which is intractable Therefore MSAT MC
is NP hard
□