В теории сложности вычислений, класс сложности 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

См. такжеПравить

ЛитератураПравить

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