Класс EXPTIME

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Свойства[править | править исходный текст]

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

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

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

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