Класс EXPTIME

Класс EXPTIME
Есть более полная статья

В теории сложности вычислений, класс сложности EXPTIME (иногда называемый просто EXP) - это множество задач, решаемых с помощью детерминированной машины Тьюринга за время O(2p(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


Формула
Wiki letter w.svg
 Для улучшения этой статьи желательно?:
  • Дополнить статью (статья слишком короткая либо содержит лишь словарное определение).
  • Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.
  • Викифицировать статью.
Классы сложности алгоритмов
 
Cчитаются лёгкими P • L • NL • AC • NC • P-complete • BQP • BPP • RP • ZPP
Предпологаются сложными NP (co-NP • NP-complete • co-NP-complete ) • UP • #P (#P-complete ) • IP • PSPACE (PSPACE-complete) • R • PP • AM
Cчитаются сложными EXPTIME • NEXPTIME • EXPSPACE • 2-EXPTIME • PR • RE • Co-RE • RE-complete • Co-RE-complete • PH
Список алгоритмов

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Полезное


Смотреть что такое "Класс EXPTIME" в других словарях:

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

  • Класс сложности — В теории алгоритмов классами сложности называются множества вычислительных задач, примерно одинаковых по сложности вычисления. Говоря более узко, классы сложности это множества предикатов (функций, получающих на вход слово и возвращающих ответ 0… …   Википедия

  • Класс NP — В теории алгоритмов классом NP (от англ. non deterministic polynomial) называют множество задач распознавания (англ.), решение которых при наличии некоторых дополнительных сведений (так называемого сертификата решения) можно «быстро» (за… …   Википедия

  • Класс PH — В теории алгоритмов классом сложности PH (от англ. polynomial hierarchy) называется объединение всех классов сложности из полиномиальной иерархии: Таким образом, предикат принадлежит классу PH, если существует такое k, что предикат принадлежит… …   Википедия

  • Класс PSPACE — В теории сложности вычислений PSPACE набор всех проблем разрешимости, которые могут быть разрешены машиной Тьюринга с полиномиальным ограничением пространства. Содержание 1 Машина Тьюринга с полиномиальным ограничением пространства …   Википедия

  • Класс NPSPACE — Содержание 1 Машина Тьюринга с полиномиальным ограничением пространства 2 Классы PSPACE, NPSPACE 3 PSPACE полные языки …   Википедия

  • Класс BPP — В теории алгоритмов классом сложности BPP (от англ. bounded error, probabilistic, polynomial) называется класс предикатов, быстро (за полиномиальное время) вычислимых и дающих ответ с высокой вероятностью (причём, жертвуя временем, можно добиться …   Википедия

  • Класс ВPP — В теории алгоритмов классом сложности BPP (от англ. bounded error, probabilistic, polynomial) называется класс предикатов, быстро (за полиномиальное время) вычислимых и дающих ответ с высокой вероятностью (причём, жертвуя временем, можно добиться …   Википедия

  • Класс P — В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отр …   Википедия

  • Класс RP — Будем считать, что язык L принадлежит классу RP («randomized polynomial class»  случайный полиномиальный), если он допускается вероятностной машиной Тьюринга M, для которой выполнены следующие условия: Если w не принадлежит L, то вероятность …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»