EXPTIME

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

[ред.ред. код]

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

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

P \subsetneq EXPTIME and NP \subsetneq NEXPTIME and PSPACE \subsetneq EXPSPACE

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

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

Визначення[ред.ред. код]

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

\text{EXPTIME} = \bigcup_{k=1}^{\infty} O\left(2^{n^k}\right)