ملخص: Abstract. Atemporal constraint language is a set of relations that has a ?rst-order de?nition in (Q;<), the dense linear order of the rational numbers. We present a complete complexity classi?cation 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. Our proof combines model-theoretic concepts with techniques from universal algebra, and also applies the so-called product Ramsey theorem, which we believe will useful in similar contexts of constraint satisfaction complexity classi?cation. An extended abstract of this article appeared in the proceedings of STOC?08.

لغة: إنجليزية