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

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

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

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

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

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

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

Визначення

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

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