The complexity of reasoning about spatial congruence

In the recent literature of Artificial Intelligence, an intensive research effort has been spent, for various algebras of qualitative relations used i n the representation of temporal and spatial knowledge, on the problem of c lassifying the computational complexity of reasoning problems for subsets o f algebras. The main purpose of these researches is to describe a restricte d set of maximal tractable subalgebras, ideally in an exhaustive fashion wi th respect to the hosting algebras. In this paper we introduce a novel algebra for reasoning about Spatial Cong ruence, show that the satisfiability problem in the spatial algebra MC-4 is NP-complete, and present a complete classification of tractability in the algebra, based on the individuation of three maximal tractable subclasses, one containing the basic relations. The three algebras are formed by 14, 10 and 9 relations out of 16 which form the full algebra.