Класс сложности EXPTIME (иногда называемый просто EXP) — это множество задач, в теории сложности вычислений, решаемых с помощью детерминированной машины Тьюринга за время O(2p(n)), где p(n) это полиномиальная функция от n.
Свойства Известно, что P NP PSPACE EXPTIME NEXPTIME EXPSPACE
Также, по теоремам :en:time hierarchy theorem и :en:space hierarchy theorem
P EXPTIME; NP NEXPTIME; PSPACE EXPSPACE
См. также Экспоненциальная сложность
Литература
Категория:Классы сложности