Клас складності EXPTIME

Експоненціальний алгоритм, EXPTIME (від англ. Exponential Time — експоненційний час) — в теорії складності обчислень, клас задач, які розв'язні на машині Тюринга за час O(2^p(n))), де p(n) — поліноміальна функція від n.

Відомо, що P ${\displaystyle \subseteq }$ NP ${\displaystyle \subseteq }$ PSPACE ${\displaystyle \subseteq }$ EXPTIME ${\displaystyle \subseteq }$ NEXPTIME ${\displaystyle \subseteq }$ EXPSPACE

і також, за теоремою про ієрархію часу та теоремою про ієрархію місця, що

P ${\displaystyle \subsetneq }$ EXPTIME and NP ${\displaystyle \subsetneq }$ NEXPTIME and PSPACE ${\displaystyle \subsetneq }$ EXPSPACE

Відомо, що якщо P = NP, то EXPTIME = NEXPTIME

До EXPTIME-повних задач належать задачі оцінки позиції в узагальнених шахах, шашках, Го.

Визначення

Алгоритми з експотенціальною складністю в термінах О-нотації формально означуються як:

${\displaystyle {\text{EXPTIME}}=\bigcup _{k=1}^{\infty }O\left(2^{n^{k}}\right)}$