Not very surprisingly, all the calculi turned out to be NP-hard, but there are interesting fragments that lead to polynomial-time algorithms. However, there is not much work on determining the practical boundaries for solving spatial and temporal reasoning problems in practice.
In the talk, I will introduce the two most common temporal and spatial calculi and report on their worst-case computational properties and on the tractability of fragments. Further, I present the results of a set of experiments performed on temporal reasoning instances. These give an indication where the "really hard" instances are and support the conclusion that the ORD-HORN relations can indeed be used to realize efficient inference methods.