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
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
© 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: