Abstrakt
Jazyk časových omezení je množina relací, která má definici prvního řádu v hustém uspořádání racionálních čísel. V článku ukazujeme úplnou klasifikaci výpočetní složitosti problému splnitelnosti pro jazyky časových omezení.
Pokud je jazyk obsažen v jednom z devíti jazyků časových omezení, pak je problém splnitelnosti rozhodnutelný v polynomiálním čase. Jinak je problém rozhodnutelnosti NP-úplný.