The Complexity of Reasoning with Relative Directions
Lee Jae Hee · Frontiers in artificial intelligence and applications · 2014
Whether reasoning with relative directions can be performed in NP has been an open problem in qualitative spatial reasoning. Efficient reasoning with relative directions is essential, for example, in rule-compliant agent navigation. In this paper, we prove that reasoning with relative directions is ∃R-complete. As a consequence, reasoning with relative directions is not in NP, unless NP=∃R.