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

Властивості

Відомо, що

P \ SubseteqNP \ SubseteqPSPACE \ Subseteq EXPTIME \ Subseteq NEXPTIME \ Subseteq EXPSPACE

Також, за теоремам en: time hierarchy theorem і en: space hierarchy theorem

P \ Subsetneq EXPTIME; NP \ Subsetneq NEXPTIME; PSPACE \ Subsetneq EXPSPACE


Вважається легкими P L NL AC NC P-complete BQP BPP RP ZPP
Предпологаются складними NP ( co-NP NP-Complete Co-NP-complete) UP # P (# P-complete) IP PSPACE (PSPACE-complete) R PP AM
Вважається складними EXPTIME NEXPTIME EXPSPACE 2-EXPTIME PR RE Co-RE RE-complete Co-RE-complete PH
Список алгоритмів