Что компьютеру сделать легко, а что почти невозможно? Эти вопросы лежат в основе вопроса вычислительной сложности. Представляем вам карту этого ландшафта.
Различные классы сложности сортируют задачи в иерархическом виде. Один класс может содержать все задачи другого, плюс задачи, требующие дополнительных вычислительных ресурсов.
Какова фундаментальная сложность задачи? Такова постановка базовой задачи специалистов по информатике, пытающихся рассортировать задачи по т.н. классам сложности. Это группы, содержащие все вычислительные задачи, требующие не более фиксированного количества вычислительных ресурсов – таких, как время или память. Возьмём простой пример с большим числом типа 123 456 789 001. Можно задать вопрос: является ли оно простым числом – таким, которое делится только на 1 и себя? Специалисты по информатике могут ответить на него при помощи быстрых алгоритмов – таких, что не начинают тормозить на произвольно больших числах. В нашем случае окажется, что это число не является простым. Затем мы можем задать вопрос: каковы его простые множители? А вот для ответа на него быстрого алгоритма не существует – только если использовать квантовый компьютер. Поэтому специалисты по информатике считают, что две этих задачи относятся к разным классам сложности.
Существует множество различных классов сложности, хотя в большинстве случаев исследователи не смогли доказать, что один класс чётко отличается от других. Доказательства различия между классами – одни из самых трудных и важных задач в этой области.
Разница между классами может быть едва различимой или явной, и хорошо разбираться во всех классах довольно трудно. Поэтому мы собрали этот справочник по семи наиболее фундаментальным классам сложности. И да не будете вы больше путать между собой BPP и BQP.
P
Обозначает: полиномиальное время
Краткое описание: все задачи, которые легко может решить классический (не квантовый) компьютер.
Точное описание: алгоритмы класса P должны прекратить работу и выдать правильный ответ не более чем за время nc, где n – длина входных данных, c – константа.
Типичные задачи:
- Является ли число простым?
- Каков кратчайший путь между двумя точками?
Что исследователи хотели бы знать: совпадает ли P с NP? Совпадение совершило бы революцию в информатике и лишило бы смысла большую часть криптографических систем (но в это почти никто не верит).
NP
Обозначает: недетерминированное полиномиальное время
Краткое описание: все задачи, которые классический компьютер может легко проверить при наличии решения.
Точное описание: проблема попадает в класс NP, когда при наличии ответа «да» существует краткое доказательство корректности ответа. Если входные данные представляют собой строку X, а вам надо решить, совпадает ли ответ с «да», тогда кратким доказательством будет другая строка, Y, которую можно использовать для проверки корректности ответа «да» за полиномиальное время. (Y иногда называют «кратким свидетелем» – у всех задач из NP есть краткие свидетели, благодаря которым их можно проверить).
Типичные задачи:
- Задача о клике. Представьте граф с рёбрами и вершинами – к примеру, вершины обозначают пользователей соцсети, а ребро – то, что они «друзья». Клика – это подмножество этого графа, в котором все люди состоят друг у друга в друзьях. О графе можно задавать следующие вопросы: есть ли в нём клика из 20 человек? 50 человек? 100? Нахождение клики – это NP-полная задача, то есть, её сложность самая высокая из всех NP-задач. Но, имея потенциальный ответ – подмножество из 50 узлов, которые могут быть или не быть кликой – проверить его легко.
- Задача коммивояжёра. Дан набор городов с расстояниями между двумя любыми парами – существует ли способ объехать все города, проехав меньше определённого расстояния? К примеру, может ли коммивояжёр объехать все столицы штатов США, проехав менее 11 000 миль?
Что исследователи хотели бы знать: P = NP? Специалисты по информатике и близко не подошли к решению этой задачи.
PH
Обозначает: полиномиальная иерархия
Краткое описание: PH – это обобщение NP. Она содержит все задачи, которые можно получить, начав с задачи из NP, и накладывая дополнительные уровни сложности.
Точное описание: PH содержит задачи с некоторым количеством различных «кванторов», усложняющих эти задачи. Пример задачи с различными кванторами: Если нам дано X, существует ли такой Y, что для каждого Z существует W, при котором выполняется R? Чем больше в задаче кванторов, тем она сложнее, и тем выше полиномиальная иерархия.
Типичная задача: определить, действительно ли существует клика размера 50, и не существует клики размером 51.
Что исследователи хотели бы знать: никто пока не смог доказать, что PH отличается от P. Эта задача эквивалентна равенству P и NP, поскольку, если вдруг окажется, что P = NP, тогда все PH низведутся до P (P = PH).
PSPACE
Обозначает: полиномиальное ограничение пространства
Краткое описание: PSPACE содержит все задачи, которые можно решить, используя разумное количество памяти.
Точное описание: При решении задач PSPACE вы уже не переживаете за время, вы переживаете только за количество памяти, которое требуется для работы алгоритма. Специалисты по информатике доказали, что PSPACE содержит PH, которая содержит NP, которая содержит P.
Типичная задача: все задачи из P, NP и PH содержатся в PSPACE.
Что исследователи хотели бы знать: отличается ли PSPACE от P?
BQP
Обозначает: квантово-полиномиальное время с ограничением вероятности ошибок
Краткое описание: все задачи, которые легко можно решить на квантовом компьютере.
Точное описание: все задачи, которые можно решить на квантовом компьютере за полиномиальное время.
Типичная задача: найти простые множители целого числа.
Что исследователи хотели бы знать: Пока что доказано, что BQP содержится в PSPACE, и что BQP содержит P. Исследователи не знают, содержится ли BQP в NP, но они считают, что два этих класса сравнивать нельзя – есть задачи, входящие в NP, но не входящие в BQP, и наоборот.
EXPTIME
Обозначает: экспоненциальное время
Краткое описание: все задачи, которые можно решить за экспоненциальное время на классическом компьютере.
Точное описание: EXP содержит все предыдущие классы — P, NP, PH, PSPACE и BQP. Исследователи доказали, что он отличается от P – они обнаружили задачи, входящие в EXP, и не входящие в P.
Типичная задача: обобщения игр типа шахмат и шашек. Если шахматная доска может быть любого размера, то задача определения наличия преимущества у одного из игроков становится задачей из EXP.
Что исследователи хотели бы знать: они хотели бы доказать, что PSPACE не содержит EXP. Они считают, что существуют задачи, входящие в EXP, но не входящие в PSPACE, потому что иногда для решения задачи из EXP требуется очень много времени. Исследователи знают, как разделять EXP и P.
BPP
Обозначает: полиномиальное время с ограничением вероятности ошибок
Краткое описание: задачи, которые можно быстро решить при помощи алгоритмов, использующих случайность.
Точное описание: BPP совпадает с P, с той разницей, что алгоритм может включать шаги, в которых принятие решений происходит случайно. Алгоритмам в BPP необходимо давать правильные ответы с вероятностью, близкой к 1.
Типичная задача: у вас есть две различные формулы, выдающие многочлены со множеством переменных. Вычисляют ли эти формулы один и тот же многочлен? Это задача проверки полиномиальной идентичности.
Что исследователи хотели бы знать: Равны ли BPP и P. Если они равны, тогда любой алгоритм со случайностями можно было бы избавить от случайностей. Они считают, что так и есть – что для каждой задачи, для которой существует эффективный случайный алгоритм, существует и эффективный детерминистский алгоритм – но пока не смогли этого доказать.
Автор: SLY_G
