Класс 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 $\subsetneq$ EXPTIME  ;    NP $\subsetneq$ NEXPTIME  ;    PSPACE $\subsetneq$ EXPSPACE

Классы сложности алгоритмов