---
title: "On the Complexity of Qualitative Spatial Reasoning: A Maximal Tractable Fragment of the Region Connection Calculus"
authors:
  - "Jochen Renz"
  - "Bernhard Nebel"
doi: ""
url: "https://ijcai.org/proceedings/1997/77"
pdf: "https://ijcai.org/proceedings/1997/0077.pdf"
venue: "Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence"
year: 1997
pages: "522-526"
track: "Diagnosis and Qualitative Reasoning"
keywords:
---

# On the Complexity of Qualitative Spatial Reasoning: A Maximal Tractable Fragment of the Region Connection Calculus

Jochen Renz, Bernhard Nebel

*Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence*, pages 522-526.

## Abstract

The computational properties of qualitative spatial reasoning have been investigated to some degree. However, the question for the boundary between polynomial and NP-hard reasoning problems has not been addressed yet. In this paper we explore this boundary in the "Region Connection Calculus" RCC-8. We extend Bennett's encoding of RCC-8 in modal logic. Based on this encoding, we prove that reasoning is NP-complete in general and identify a maximal tractable subset of the relations in RCC-8 that contains all base relations. Further, we show that for this subset path-consistency is sufficient for deciding consistency.