Publication at Faculty of Mathematics and Physics |
2010
Abstract
A temporal constraint language is a set of relations that has a first-order definition in the dense linear order of the rational numbers. We present a complete complexity classification of the constraint satisfaction problem (CSP) for temporal constraint languages: if the constraint language is contained in one out of nine temporal constraint languages, then the CSP can be solved in polynomial time; otherwise, the CSP is NP-complete.