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

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

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

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

#П	Подсчитайте решения проблемы NP
# P-complete	Самые сложные проблемы в #P
2-EXPTIME	Решается за дважды экспоненциальное время
AC⁰	Класс сложности схемы ограниченной глубины
АКК⁰	Класс сложности схемы с ограниченной глубиной и счетными элементами
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	Объединение классов в полиномиальная иерархия
п^НП	Решается за полиномиальное время с оракул за проблему в НП; также известный как Δ₂п
PP	Вероятностно-полиномиальный (ответ правильный с вероятностью чуть больше ½)
PPAD	Аргументы полиномиальной четности на ориентированных графах
PR	Решается путем рекурсивного построения арифметических функций.
PSPACE	Решаемо с полиномиальным пространством.
PSPACE-полный	Самые сложные проблемы в PSPACE.
PTAS	Схема полиномиальной аппроксимации (подкласс APX).
р	Решается за конечное время.
RE	Проблемы, на которые мы можем ответить «ДА» за конечный промежуток времени, но ответ «НЕТ» может никогда не прийти.
RL	Решается в логарифмическом пространстве с помощью рандомизированных алгоритмов (НЕТ ответ, вероятно, правильный, ДА, безусловно, правильный)
RP	Решается за полиномиальное время с помощью рандомизированных алгоритмов (НЕТ ответ, вероятно, правильный, ДА, безусловно, правильный)
SL	Проблемы лог-пространства сводятся к определению, существует ли путь между заданными вершинами в неориентированном графе. В октябре 2004 г. было обнаружено, что этот класс фактически равен L.
S₂п	однораундовые игры с одновременными ходами, детерминированными за полиномиальное время^[2]
TFNP	Полные функциональные задачи, решаемые за недетерминированное полиномиальное время. Проблема в этом классе обладает тем свойством, что каждый input имеет выход, достоверность которого можно эффективно проверить, и вычислительная задача состоит в том, чтобы найти допустимый выход.
ВВЕРХ	Однозначные недетерминированные функции Polytime.
ZPL	Решается рандомизированными алгоритмами (ответ всегда правильный, среднее использование пространства логарифмическое)
ЗПП	Решается рандомизированными алгоритмами (ответ всегда правильный, среднее время выполнения полиномиально)

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

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

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

Зоопарк сложности - список более 500 классов сложности и их свойства

[complex-1] а ^б ^c Санджив Арора, Боаз Барак (2009), Вычислительная сложность: современный подход, Издательство Кембриджского университета; 1 издание, ISBN 978-0-521-42426-4

[2] "S₂П: Второй уровень симметричной иерархии ». Зоопарк сложности Стэнфордского университета. Архивировано из оригинал на 2012-10-14. Получено 2011-10-27.

[1]

[2]