The complexity of reasoning with relative directions

Publication Type:
Conference Proceeding
Citation:
Frontiers in Artificial Intelligence and Applications, 2014, 263 pp. 507 - 512
Issue Date:
2014-01-01
Full metadata record
© 2014 The Authors and IOS Press. 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 ∃ℝ-complete. As a consequence, reasoning with relative directions is not in NP, unless NP=∃ℝ.
Please use this identifier to cite or link to this item: