Лучшие вопросы
Таймлайн
Чат
Перспективы

Класс EXPTIME

Из Википедии, свободной энциклопедии

Класс EXPTIME
Remove ads

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

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

Свойства

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

P NP PSPACE EXPTIME NEXPTIME EXPSPACE

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

P EXPTIME  ;    NP NEXPTIME  ;    PSPACE EXPSPACE
Remove ads

См. также

Литература

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

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads