WikiDer > Список классов сложности

List of complexity classes

Это Список классы сложности в теория сложности вычислений. По другим вычислительным и сложным предметам см. список тем о вычислимости и сложности.

У многих из этих классов есть «напарник», который состоит из дополняет всех языков в исходном классе. Например, если язык L находится в NP, то дополнение к L находится в co-NP. (Это не означает, что дополнение NP является co-NP - есть языки, о которых известно, что они присутствуют на обоих, и другие языки, о которых известно, что они не на обоих.)

«Самые сложные проблемы» класса относятся к проблемам, которые принадлежат этому классу, так что любая другая проблема этого класса может быть сведена к нему. Кроме того, сокращение также является проблемой данного класса или его подмножества.

#ППодсчитайте решения проблемы NP
# P-completeСамые сложные проблемы в #P
2-EXPTIMEРешается за дважды экспоненциальное время
AC0Класс сложности схемы ограниченной глубины
АКК0Класс сложности схемы с ограниченной глубиной и счетными элементами
ACКласс сложности схемы
AHАрифметическая иерархия
APКласс проблем чередующиеся машины Тьюринга можно решить за полиномиальное время.[1]
APXПроблемы оптимизации которые имеют алгоритмы аппроксимации с постоянным коэффициентом аппроксимации[1]
AMРазрешается за полиномиальное время Протокол Артура-Мерлина[1]
BPPРешается за полиномиальное время с помощью рандомизированные алгоритмы (ответ наверное правильный)
BQPРешается за полиномиальное время на квантовый компьютер (ответ, наверное, правильный)
со-НПОтветы «НЕТ» можно проверить за полиномиальное время недетерминированной машиной
совместно NP-полныйСамые сложные проблемы в ко-НП
DSPACE (f (п))Решается на детерминированной машине с пространством O (f (п)).
DTIME (f (п))Решается детерминированной машиной за время O (f (п)).
EРешается экспоненциально с линейным показателем
НАЧАЛЬНЫЙОбъединение классов в экспоненциальная иерархия
ESPACEРешаемо с экспоненциальным пространством с линейным показателем
EXPТо же, что и EXPTIME
EXPSPACEРешаемо с экспоненциальным пространством
EXPTIMEРешаемо за экспоненциальное время
ФНПАналог НП для функциональные проблемы
FPАналог P для функциональных задач
FPНПАналог PНП для функциональных проблем; дом задача коммивояжера
FPTУстойчивый к фиксированным параметрам
GapLЛогпространственно сводится к вычислению целочисленного определителя матрицы
IPРазрешается за полиномиальное время интерактивная система доказательства
LРешается в логарифмическом (маленьком) пространстве
LOGCFLЛогпространство сводится к контекстно-свободный язык
MAРешается за полиномиальное время с помощью Протокол Мерлина-Артура
NCЭффективно решается (за полилогарифмическое время) на параллельных компьютерах
NEРешается недетерминированной машиной за экспоненциальное время с линейной экспонентой
NESPACEРешается недетерминированной машиной с экспоненциальным пространством с линейным показателем
NEXPТо же, что и NEXPTIME
NEXPSPACEРешается недетерминированной машиной с экспоненциальным пространством
NEXPTIMEРешается недетерминированной машиной за экспоненциальное время
NLОтветы «ДА» проверяются с помощью логарифмического пробела
НЕЭЛЕМЕНТАРНЫЙДополнение НАЧАЛЬНЫЙ.
НП«ДА» ответы проверяются за полиномиальное время (см. классы сложности P и NP)
НП-полныйСамые сложные и выразительные задачи в НП
NP-easyАналог PНП для функциональные проблемы; другое название для FPНП
NP-эквивалентСамые сложные проблемы в FPНП
NP-жесткийПо крайней мере, такая же сложная, как и любая проблема в NP, но не относится к тому же классу сложности
NSPACE (f (п))Решается недетерминированной машиной с пространством O (f (п)).
NTIME (f (п))Решается недетерминированной машиной за время O (f (п)).
пРешаемо за полиномиальное время
P-полныйСамые сложные задачи в P для решения на параллельных компьютерах
П / полиРешается за полиномиальное время с учетом «строки совета», зависящей только от размера ввода
PCPВероятностно проверяемое доказательство
PHОбъединение классов в полиномиальная иерархия
пНПРешается за полиномиальное время с оракул за проблему в НП; также известный как Δ2п
PPВероятностно-полиномиальный (ответ правильный с вероятностью чуть больше ½)
PPADАргументы полиномиальной четности на ориентированных графах
PRРешается путем рекурсивного построения арифметических функций.
PSPACEРешаемо с полиномиальным пространством.
PSPACE-полныйСамые сложные проблемы в PSPACE.
PTASСхема полиномиальной аппроксимации (подкласс APX).
рРешается за конечное время.
REПроблемы, на которые мы можем ответить «ДА» за конечный промежуток времени, но ответ «НЕТ» может никогда не прийти.
RLРешается в логарифмическом пространстве с помощью рандомизированных алгоритмов (НЕТ ответ, вероятно, правильный, ДА, безусловно, правильный)
RPРешается за полиномиальное время с помощью рандомизированных алгоритмов (НЕТ ответ, вероятно, правильный, ДА, безусловно, правильный)
SLПроблемы лог-пространства сводятся к определению, существует ли путь между заданными вершинами в неориентированном графе. В октябре 2004 г. было обнаружено, что этот класс фактически равен L.
S2поднораундовые игры с одновременными ходами, детерминированными за полиномиальное время[2]
TFNPПолные функциональные задачи, решаемые за недетерминированное полиномиальное время. Проблема в этом классе обладает тем свойством, что каждый input имеет выход, достоверность которого можно эффективно проверить, и вычислительная задача состоит в том, чтобы найти допустимый выход.
ВВЕРХОднозначные недетерминированные функции Polytime.
ZPLРешается рандомизированными алгоритмами (ответ всегда правильный, среднее использование пространства логарифмическое)
ЗППРешается рандомизированными алгоритмами (ответ всегда правильный, среднее время выполнения полиномиально)

использованная литература

  1. ^ а б c Санджив Арора, Боаз Барак (2009), Вычислительная сложность: современный подход, Издательство Кембриджского университета; 1 издание, ISBN 978-0-521-42426-4
  2. ^ "S2П: Второй уровень симметричной иерархии ». Зоопарк сложности Стэнфордского университета. Архивировано из оригинал на 2012-10-14. Получено 2011-10-27.

внешние ссылки