Класс сложности

Класс сложности

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

Для каждого класса существует категория задач, которые являются «самыми сложными». Это означает, что любая задача из класса сводится к такой задаче, и притом сама задача лежит в классе. Такие задачи называют полными задачами для данного класса. Наиболее известными являются NP-полные задачи.

Полные задачи — хороший инструмент для доказательства равенства классов. Достаточно для одной такой задачи предоставить алгоритм, решающий её и принадлежащий более маленькому классу, и равенство будет доказано.

Содержание

Определение

Каждый класс сложности (в узком смысле) определяется как множество предикатов, обладающих некоторыми свойствами. Типичное определение класса сложности выглядит так:

Классом сложности X называется множество предикатов P(x), вычислимых на машинах Тьюринга и использующих для вычисления O(f(n)) ресурса, где n — длина слова x.

В качестве ресурсов обычно берутся время вычисления (количество рабочих тактов машины Тьюринга) или рабочая зона (количество использованных ячеек на ленте во время работы). Языки, распознаваемые предикатами из некоторого класса (то есть множества слов, на которых предикат возвращает 1), также называются принадлежащими тому же классу.

Кроме того, многие классы могут также быть описаны в терминах математической логики или теории игр.

Классы принято обозначать прописными буквами. Дополнение к классу C (то есть класс языков, дополнения которых принадлежат C) обозначается co-C.

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

Отношения между классами

Все классы сложности находятся в иерархическом отношении: одни включают в себя другие. Однако про большинство включений неизвестно, являются ли они строгими. Одна из наиболее известных открытых проблем в этой области — равенство классов P и NP. Если это предположение верно (в чём большинство учёных сомневается), то представленная справа иерархия классов сильно свернётся. На данный момент наиболее распространённой является гипотеза о невырожденности иерархии (то есть все классы различны). Кроме того, известно, что EXPSPACE не равен классу PSPACE.

Иерархия по времени и иерархия по памяти

Рассмотрим функцию f и входную цепочку длиной n. Тогда класс DTIME(f(n)) определяют как класс языков, принимаемых детерминированными машинами Тьюринга, заканчивающими свою работу за время, не превосходящее f(n). Класс NTIME(f(n)), в свою очередь, определяют как класс языков, принимаемых недетерминированной машиной Тьюринга, заканчивающими свою работу за время, не превосходящее f(n). Отметим, что ограничения на память при определении данных классов отсутствуют.

Аналогично иерархии по времени вводится иерархия по памяти. Класс DSPACE(f(n)) обозначает класс языков, принимаемых детерминированными машинами Тьюринга, использующих не более f(n) ячеек памяти на рабочих лентах. Класс NSPACE(f(n)) определяют как класс языков, принимаемых недетерминированными машинами Тьюринга, использующих не более f(n) ячеек памяти на рабочих лентах. Временные ограничения при определении данных классов отсутствуют.

Аналогично определяются и другие подобные рассмотренным выше классы. Приведем использующиеся сокращения:

  • D - детерминированный (детерминистический)
  • N - недетерминированный
  • R - вероятностный с ограниченной односторонней ошибкой
  • B - вероятностный с ограниченной двусторонней ошибкой
  • BQ - квантовый с ограниченной двусторонней ошибкой

См. также

Классы сложности алгоритмов
 
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
Список алгоритмов


Литература

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

Ссылки


Информатика
Text document with red question mark.svg
 В данной статье или разделе имеется список источников или внешних ссылок, но источники отдельных утверждений остаются неясными из-за отсутствия сносок.
Вы можете улучшить статью, внеся более точные указания на источники.

Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Полезное


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

  • класс сложности (для систем экологического менеджмента) — 3.5 класс сложности (для систем экологического менеджмента): Характер, количество и значимость экологических аспектов организации, которые существенно влияют на время, затрачиваемое аудитором. Источник …   Словарь-справочник терминов нормативно-технической документации

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

  • Класс Sharp-P — Правильный заголовок этой статьи  Класс #P. Он показан некорректно из за технических ограничений. В теории сложности, #P является классом проблем, решением которых является количество успешных, т.е., завершающихся в допускающих состояниях,… …   Википедия

  • класс — 3.7 класс : Совокупность подобных предметов, построенная в соответствии с определенными правилами. Источник: ГОСТ Р 51079 2006: Технические средства реабилитации людей с ограничениями жизнедеятельности. Классификация …   Словарь-справочник терминов нормативно-технической документации

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

  • Класс co-NP — В теории алгоритмов часто рассматривается класс, тесно связанный с P и NP,  класс дополнений языков из NP, называемый co NP. Формальное определение Класс сложности co NP определяется для множества языков, то есть множеств слов над конечным… …   Википедия

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

  • Класс сo-NP — В теории алгоритмов часто рассматривается класс, тесно связанный с P и NP, класс дополнений языков из NP, называемый co NP. Формальное определение Класс сложности co NP определяется для множества языков, т.е. множеств слов над конечным алфавитом… …   Википедия

  • КЛАСС ПАУКООБРАЗНЫЕ ИЛИ АРАХНИДЫ (ARACHNIDA) —          Паукообразные, или арахниды (Агаchnida)1, это собрание всех наземных хелицеровых.         Латинское название класса, в этой транскрипции теперь более принятое, прежде писалось Arachnoidea.         Арахна по гречески «паук». В… …   Биологическая энциклопедия

  • КЛАСС ИНФУЗОРИИ (INFUSORIA или CILIATA) —          Простейшие этого обширного по количеству видов около 6 тыс. класса широко распространены в природе. (Эта цифра приводится в сводке Корлисса, 1961 г.). К ним относятся многочисленные обитатели морских и пресных вод. Некоторые виды… …   Биологическая энциклопедия


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

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