Класс EXPTIME

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

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

Свойства

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

P $\subseteq$ NP $\subseteq$ PSPACE $\subseteq$ EXPTIME $\subseteq$ NEXPTIME $\subseteq$ EXPSPACE

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

P $⊊$ EXPTIMEШаблон:Nbsp; Шаблон:Nbsp NP $⊊$ NEXPTIMEШаблон:Nbsp; Шаблон:Nbsp PSPACE $⊊$ EXPSPACE

См. также

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

Литература

• Шаблон:Книга