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

Это список классов сложности в теории сложности вычислений . Информацию о других темах, связанных с вычислениями и сложностью, см. в списке тем, посвященных вычислимости и сложности .

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

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

#П	Подсчитайте решения задачи NP
#P-полное	Самые сложные проблемы в #P
2-ВРЕМЯ ЭКСПЛУАТАЦИИ	Решаема за дважды экспоненциальное время.
переменного тока ⁰	Класс сложности схемы ограниченной глубины
АСС ⁰	Класс сложности схемы с ограниченной глубиной и счетными вентилями
переменного тока	Класс сложности схемы
АХ	Арифметическая иерархия
АП	Класс задач, которые чередующиеся машины Тьюринга могут решить за полиномиальное время. ^[1]
АПХ	Задачи оптимизации , имеющие алгоритмы аппроксимации с постоянным коэффициентом аппроксимации. ^[1]
ЯВЛЯЮСЬ	Решается за полиномиальное время по протоколу Артура – Мерлина. ^[1]
БПП	Решается за полиномиальное время с помощью рандомизированных алгоритмов (вероятно, ответ правильный)
Министерство национальной обороны	Решаема за полиномиальное время на квантовом компьютере (вероятно, ответ правильный)
со-НП	Ответы «НЕТ» проверяются за полиномиальное время недетерминированной машиной.
со-NP-полный	Самые сложные проблемы в ко-НП
DLIN	Решается с помощью детерминированной многоленточной машины Тьюринга за время O( n ).
ДСПЕЙС(е( п ))	Решается детерминированной машиной с пространством O(f( n )).
ДВРЕМЯ(f( n ))	Решается детерминированной машиной за время O(f( n )).
И	Решаемо за экспоненциальное время с линейным показателем
ЭЛЕМЕНТАРНЫЙ	Объединение классов в экспоненциальной иерархии
КОСМОС	Решаемо в экспоненциальном пространстве с линейным показателем
Опыт	То же, что EXPTIME
EXPSPACE	Решаемо в экспоненциальном пространстве
ВРЕМЯ ЭКСПРЕСС	Решаемо за экспоненциальное время
ФНП	Аналог NP для функциональных задач
ФП	Аналог P для функциональных задач
ФП ^{НАПРИМЕР}	Аналог П ^{НАПРИМЕР} при функциональных проблемах; Дом коммивояжера» Задача «
ФПТ	управляемый с фиксированными параметрами
ГэпЛ	Сводима в лог-пространстве к вычислению целочисленного определителя матрицы
ИП	Решается за полиномиальное время с помощью интерактивной системы доказательств.
л	Решаемо с логарифмическим (малым) пространством.
ЛОГКФЛ	Сводимость пространства журналов к контекстно-свободному языку
И	Решается за полиномиальное время по протоколу Мерлина – Артура.
Северная Каролина	Эффективно решаемо (за полилогарифмическое время) на параллельных компьютерах.
NE	Решается недетерминированной машиной за экспоненциальное время с линейным показателем.
НЕСПАС	Решается с помощью недетерминированной машины с экспоненциальным пространством с линейным показателем.
НЕКСП	То же, что и NEXPTIME
НЕКСПСПЕЙС	Решается с помощью недетерминированной машины с экспоненциальным пространством.
СЛЕДУЮЩЕЕ ВРЕМЯ	Решается недетерминированной машиной за экспоненциальное время.
Нидерланды	Ответы «ДА» проверяются с помощью логарифмического интервала.
НЛИН	Решается с помощью недетерминированной многоленточной машины Тьюринга за время O( n ).
НЕЭЛЕМЕНТАРНЫЙ	Дополнение ЭЛЕМЕНТАРНО .
НАПРИМЕР	Ответы «ДА» проверяются за полиномиальное время (см. классы сложности P и NP )
NP-полный	Самые сложные и выразительные задачи в NP.
NP-легко	Аналог П ^{НАПРИМЕР} для функциональных проблем ; другое название ФП ^{НАПРИМЕР}
NP-эквивалент	Самые сложные проблемы в ФП ^{НАПРИМЕР}
NP-жесткий	По крайней мере, так же сложно, как и все задачи в NP, но неизвестно, что они относятся к тому же классу сложности.
NSPACE(f( n ))	Решается недетерминированной машиной с пространством O(f( n )).
НВРЕМЯ(f( n ))	Решается недетерминированной машиной за время O(f( n )).
П	Решаема за полиномиальное время
P-полный	Самые сложные задачи в P для решения на параллельных компьютерах
П/поли	Решается за полиномиальное время с учетом «строки совета», зависящей только от размера входных данных.
PCP	Вероятностно проверяемое доказательство
PH	Объединение классов полиномиальной иерархии
П ^{НАПРИМЕР}	Решаема за полиномиальное время с помощью оракула для задачи NP; также известный как Δ ₂ P
ПП	Вероятностно-полиномиальный (ответ правильный с вероятностью чуть больше ½)
ППАД	Аргументы полиномиальной четности на ориентированных графах
пиар	Решается рекурсивным построением арифметических функций.
PSPACE	Разрешимо в полиномиальном пространстве.
PSPACE-полный	Самые сложные задачи в PSPACE.
ПТАС	Схема аппроксимации полиномиального времени (подкласс APX).
QIP	Решается за полиномиальное время с помощью квантовой интерактивной системы доказательств.
КМА	Квантовый аналог NP .
Р	Решается за конечное время.
РЭ	Проблемы, на которые мы можем ответить «ДА» за ограниченное время, но ответ «НЕТ» может никогда не прийти.
РЛ	Решается в логарифмическом пространстве с помощью рандомизированных алгоритмов (НЕТ ответа, вероятно, правильный, ДА, безусловно, правильный)
РП	Решается за полиномиальное время с помощью рандомизированных алгоритмов (НЕТ ответа, вероятно, правильный, ДА, безусловно, правильный)
СЛ	Проблемы лог-пространства, сводимые к определению существования пути между заданными вершинами неориентированного графа. что этот класс на самом деле равен L. В октябре 2004 года было обнаружено ,
С ₂ П	однотуровые игры с одновременными ходами судятся детерминированно за полиномиальное время ^[2]
ТФНП	Задачи с полными функциями, решаемые за недетерминированное полиномиальное время. Задача этого класса обладает тем свойством, что каждый входной сигнал имеет выходной результат, достоверность которого можно эффективно проверить, и вычислительная задача состоит в том, чтобы найти действительный выходной сигнал.
ВВЕРХ	Однозначные недетерминированные функции Polytime.
ЗПЛ	Решается с помощью рандомизированных алгоритмов (ответ всегда правильный, среднее использование пространства логарифмическое)
ЗПП	Решается с помощью рандомизированных алгоритмов (ответ всегда правильный, среднее время работы полиномиально)

Ссылки [ править ]

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

Внешние ссылки [ править ]

Зоопарк сложности — список из более чем 500 классов сложности и их свойств.

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

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

[1]

[2]