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

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

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

Содержание

• 
  1Определение
  
• 
  2Отношения между классами
  
• 
  3Иерархия по времени и иерархия по памяти
  
• 
  4См. также
  
• 
  5Литература
  
• 
  6Ссылки
  

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

Классом сложности 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 — квантовый с ограниченной двусторонней ошибкой