A Complete Classification of Tractability in RCC-5
  We investigate the computational properties of the spatial algebra RCC-5
which is a restricted version of the RCC framework for spatial reasoning. The
satisfiability problem for RCC-5 is known to be NP-complete but not much is
known about its approximately four billion subclasses. We provide a complete
classification of satisfiability for all these subclasses into polynomial and
NP-complete respectively. In the process, we identify all maximal tractable
subalgebras which are four in total.
