On point-based temporal disjointness

摘要

We address the problems of determining consistency and of finding a solution for sets of three-point relations expressing exclusion of a point from an interval, and for sets of four-point relations expressing interval disjointness. Availability of these relations is an important requirement for dealing with the sorts of temporal constraints encountered in many AI applications such as plan reasoning. We prove that consistency testing is NP-complete and finding a solution is NP-hard.