A Complete Classification of Tractability in RCC-5
<|reference_start|>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.<|reference_end|>
@article{jonsson1997a,
    title={A Complete Classification of Tractability in RCC-5},
    author={P. Jonsson, T. Drakengren},
    journal={Journal of Artificial Intelligence Research, Vol 6, (1997),
  211-221},
    year={1997},
    archivePrefix={arXiv},
    eprint={cs/9706102},
    primaryClass={cs.AI}
}