Експоненціальний алгоритм, EXPTIME (від англ. Exponential Time — експоненційний час) — в теорії складності обчислень, клас задач, які розв'язні на машині Тюринга за час O(2p(n))), де p(n) — поліноміальна функція від n.
ред.
Відомо, що P NP PSPACE EXPTIME NEXPTIME EXPSPACE
і також, за теоремою про ієрархію часу та теоремою про ієрархію місця, що
Відомо, що якщо P = NP, то EXPTIME = NEXPTIME
До EXPTIME-повних задач належать задачі оцінки позиції в узагальнених шахах, шашках, Го.
Визначення ред.
Алгоритми з експотенціальною складністю в термінах О-нотації формально означуються як: