Treffer: The Computational Complexity of Relating Points with Intervals on the Real Line

Vilain has suggested the point-interval algebra for reasoning about the relative positions of points and intervals on the real line. The satisfiability problem for the full point-interval algebra is known to be NP-complete but the computational complexity of its 4; 294; 967; 296 subclasses has not been investigated. We classify these subclasses with respect to whether their corresponding satisfiability problems are polynomial-time or NP-complete. The classification reveals that there are exactly five maximal subclasses having a polynomial-time satisfiability problem. 27 1 Introduction Problems concerned with the realizability of a set of points or intervals (along the real line) subject to constraints have been a very active research area for some time. Such problems arise in several application areas including operations research [ Papadimitriou and Yannakakis, 1979 ] , combinatorics [ Roberts, 1976 ] , planning [ Allen, 1991 ] , natural language processing [ Song and Cohen, 1988.