Complexity classification in qualitative temporal constraint reasoning Original Research Article

We study the computational complexity of the qualitative algebra which is a temporal constraint formalism that combines the point algebra, the point-interval algebra and Allenʹs interval algebra. We identify all tractable fragments and show that every other fragment is NP-complete.