Класс сложности EXPTIME (иногда называемый просто EXP) — это множество задач, в теории сложности вычислений, решаемых с помощью детерминированной машины Тьюринга за время O(2p(n)), где p(n) это полиномиальная функция от n.
Энциклопедичный YouTube
-
1/3Просмотров:29 699 8278 66120 205
-
Science Experiment LIQUID NITROGEN vs PEPSI
-
История и процесс производство автомобилей Bentley
-
Audi Q7 - отличный внедорожник премиум класса
Субтитры
Свойства
Известно, что
Также, по теоремам 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.
Обычно почти сразу, изредка в течении часа.