EXPTIME

W obliczeniowej teorii złożoności klasa złożoności EXPTIME (czasami nazywana EXP lub DEXPTIME) jest zbiorem wszystkich problemów decyzyjnych, które mają wykładniczy czas wykonywania, tj. są rozwiązywalne przez deterministyczną maszynę Turinga w czasie O (2^p(n)), gdzie p(n) jest funkcją wielomianową n.

Definicja używająca DTIME:

${\displaystyle {\mathsf {EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}\left(2^{n^{k}}\right)}$

Wiemy, że:

P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE,

a także według twierdzenia o hierarchii czasu i twierdzenia o hierarchii przestrzeni, że

P ⊊ EXPTIME, NP ⊊ NEXPTIME and PSPACE ⊊ EXPSPACE,

więc co najmniej jedna z pierwszych trzech inkluzji i co najmniej jedna z trzech ostatnich inkluzji muszą być właściwe, ale nie wiadomo, które z nich są. Większość ekspertów uważa, że wszystkie inkluzje są prawidłowe. Wiadomo również, że jeśli P = NP, to EXPTIME = NEXPTIME, klasa problemów możliwych do rozwiązania w czasie wykładniczym przez niedeterministyczną maszynę Turinga^[1]. Dokładniej, EXPTIME ≠ NEXPTIME wtedy i tylko wtedy, gdy istnieją rzadkie języki w NP, które nie są w P^[2].

EXPTIME można również przeformułować jako klasę przestrzeni APSPACE, problemy, które można rozwiązać za pomocą naprzemiennej maszyny Turinga w przestrzeni wielomianowej. Jest to jeden ze sposobów, aby zobaczyć PSPACE ⊆ EXPTIME, ponieważ naprzemienna maszyna Turinga jest co najmniej tak potężna jak deterministyczna maszyna Turinga^[3].