
| Rel of M C   | Rel of RCC     |
|--------------|----------------|
| CG           | {EQ, DR, PO}   |
| CGPP         | {PP, DR, PO}   |
| CGPP         | {bb-', DR, PO} |
| CNO          | {DR, PO}       |

Table The basic relations of MC and their counterparts in RCC
The meaning of the Table is that when a relation of MC is established then one of the relations of in second column is established as well RCC

| Rel of RCC   | Rel of MC               |        |
|--------------|-------------------------|--------|
| EQ           | CG                      |        |
| PP           | CGPP                    |        |
| PP           | C GPP-                  |        |
| PO           | {CG, CGPP, CGPP-1, CNO} |        |
| DR           | {CG, CGPP, CGPPT        | 1 CNO} |

Table RCC
namely x is disjoint from y Then  each relation of MC    can be established between x and y  However  if x PP y  namely x is a proper part of y  then only the CGPP relation can be established between x and y  On the other hand  if two regions are congruent  only the relations DR PO and EQ can exist between x and y In Table   we set the correspondences between MC   basic relations and RCC
while in Table   we set the correspondences between RCC   and MC
The correspondences of the above Tables are not sufficiently strict  to use them in prov ing that MSAT MC   is an NP complete problem by a direct polynomial reduction  If we consider a CSP on MC   the corresponding RCC   CSP is not intractable since the relations obtained from Table do not define an intractable subset of RCC
by means of the complete classification established by Jonsson and Drakengren Therefore MM
the RSAT symbol represents the satisfi ability in RCC models  by the corresponding relation mapping of Table Conversely  we can establish  by means of the above Tables  that among all the possible regions satisfying the relation CG  there exists at least one pair in which the regions are EQ that when CGPP is established there exists one pair in a PP relation and finally that when CNO is established we have two regions in a PO relation  The summary of this correspondence is reported in Table This correspondence is obtained from the definition of basic relations  Two regions a and b are congruent iff we can roto translate a by a T in such a way that T a  EQ b or conversely by T ′ so that T ′ b EQ a Analogously a is congruent to a part of b iff we can