Alfonso Gerevini and Lenhart Schubert, 
<I> On point-based temporal disjointness</I>, University of Rochester,
Computer Science Department, Technical Report 407, March 1994. 
<P> 

One of the main problems in knowledge representation is checking
consistency. In the paper under review, the consistency of temporal
knowledge is considered, i.e., of knowledge about moments and
intervals of time that correspond to different events. The authors
show that even if we consider only knowledge consisting of the
statements "intervals $[a^-,a^+]$ and $[b^-,b^+]$ are disjoint" and
"moment $a$ precedes moment $b$" (i.e., $a<b$), 
then the consistency problem is NP-hard. This problem remains
NP-hard even if we only consider the above disjointness 
statements in which one of
the intervals $[a^-,a^+]$ is "degenerate" ($a^-=a^+$).