
## Cdc Is Decidable.

The consistency checking problems with the CDC and/or akin formalisms have been discussed in several literatures [3, 15, 16, 10]. In particular, Liu et al. [10] provided a cubic algorithm for checking the consistency of complete networks of basic CDC constraints, and proved that reasoning with the CDC in general is an NP-Complete problem.

This means **RSAT**(Bdir) is tractable but **RSAT**(CDC) is not, where Bdir represents the set of all basic CDC relations. Before this work, we did not know if the CDC has larger tractable subclasses, not to mention finding maximal tractable subclasses and determining the boundary between the tractable and intractable subclasses of the CDC.

To find maximal tractable subclasses of a qualitative calculus, an often used technique is to propagate the tractability of a subclass to its closure in the calculus under converse, intersection, and weak composition. This technique was first developed in reasoning with the IA [11], and then applied to reasoning with RCC8 [14, 9] and general qualitative calculi in which path-consistency decides the consistency of a complete basic network
[13]. Because the CDC does not have this property, the applicability of this technique is not immediately clear.

When discussing topological inference, Grigni et al. [7] distinguished between two important special cases of constraint networks that are of interest: In the *explicit* case, all constraints are basic (the relation for each pair of variables is specified). In the *conjunctive* case some constraints are basic while all the others are unspecified. This latter situation
"arises in geographic applications where the relation between objects in the same map is known, but not explicit information is given about objects in different maps. [7]"
The consistency decision problem of explicit constraint networks corresponds to **RSAT**(Bdir),
and that of conjunctive constraint networks corresponds to **RSAT**(Bdir *∪ {∗}*), where ∗ is the universal relation, i.e. the union of all basic relations. Having seen that Bdir is a tractable subclass of the CDC [10], we are inclined to believe that Bdir *∪ {∗}* is also a tractable subclass of the CDC. This paper, however, shows that this is not the case.

Note that the universal relation is the weak composition of two basic CDC relations [10].

This suggests that the propagation technique used in e.g. [11, 14, 9, 13] fails to find the maximal tractable subclasses of the CDC.

It seems that the CDC is the *first* qualitative calculus in which reasoning with conjunctive constraints has different complexity as reasoning with explicit constraints.

We obtain the result by showing that there is a polynomial reduction from the 3-SAT
problem to **RSAT**(Bdir *∪ {∗}*). The reduction is devised based on the observation that some *non-CDC* relations are *definable* in the CDC (see Definition 2). In particular, the upper left corner (ULC) relation is defined by using only basic CDC constraints, where two bounded regions have the ULC relation if their minimum bounding rectangles (mbrs)
are incomparable but have the same upper left corner point (see Figure 1 for illustrations).