Класс EXPTIME

Иерархия классов сложности.

Класс сложности EXPTIME (иногда называемый просто EXP) — это множество задач, в теории сложности вычислений, решаемых с помощью детерминированной машины Тьюринга за время O(2^p(n)), где p(n) это полиномиальная функция от n.

Свойства

Известно, что

P [math]\displaystyle{ \subseteq }[/math] NP [math]\displaystyle{ \subseteq }[/math] PSPACE [math]\displaystyle{ \subseteq }[/math] EXPTIME [math]\displaystyle{ \subseteq }[/math] NEXPTIME [math]\displaystyle{ \subseteq }[/math] EXPSPACE

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

P [math]\displaystyle{ \subsetneq }[/math] EXPTIME  ;    NP [math]\displaystyle{ \subsetneq }[/math] NEXPTIME  ;    PSPACE [math]\displaystyle{ \subsetneq }[/math] EXPSPACE

См. также

• Экспоненциальная сложность

Литература

• Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — 528 с. — ISBN 0-201-44124-1.