WikiSort.ru - Не сортированное

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

Свойства

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

P ${\displaystyle \subseteq }$ NP ${\displaystyle \subseteq }$ PSPACE ${\displaystyle \subseteq }$ EXPTIME ${\displaystyle \subseteq }$ NEXPTIME ${\displaystyle \subseteq }$ EXPSPACE

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

P ${\displaystyle \subsetneq }$ EXPTIME  ;    NP ${\displaystyle \subsetneq }$ NEXPTIME  ;    PSPACE ${\displaystyle \subsetneq }$ EXPSPACE

См. также

• Экспоненциальная сложность

Литература

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

Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её.

Для улучшения этой статьи желательно: Найти и оформить в виде сносок ссылки на независимые авторитетные источники, подтверждающие написанное. Викифицировать статью.

В другом языковом разделе есть более полная статья EXPTIME (англ.). Вы можете помочь проекту, расширив текущую статью с помощью перевода. При этом, для соблюдения правил атрибуции, следует установить шаблон {{переведённая статья}} на страницу обсуждения, либо указать ссылку на статью-источник в комментарии к правке.