Список классов сложности - List of complexity classes

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

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

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

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

Рекомендации

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