Постановка проблемы

• Существует ряд задач, для которых поиск эффективного обобщённого алгоритма решения, скорее всего, является пустой тратой времени
• Для таких задач, как правило, более полезным будет найти приближённое решение или решение для частного случая
• Чтобы доказать, что задача является таковой, вводятся классы сложности

Класс сложности $P$

• Класс сложности $P$ содержит наиболее простые задачи, а именно, задачи, решаемые за полиномиальное время
• Более формально: задача принадлежит классу $P$, если существует алгоритм, решающий её за время $O(N^k)$, где $N$ — объём задачи, $k$ — некоторая константа
• К этому классу относится большинство рассмотренных нами задач

Почему именно полином

• В теории легко представить задачу, решаемую за полиномиальное время, но при этом являющуюся достаточно сложной
• К примеру, задача, решаемая алгоритмом за время $O(N^{100})$ относится к классу $P$, однако, очевидно, не является вычислительно простой
• Однако на практике подобные задачи встречаются крайне редко
• Как правило, степень полинома не превосходит $3$

Почему именно полином

• Более того, практика показывает, что, даже если на данный момент алгоритм решения задачи работает за полином степени больше $3$, скорее всего, в скором времени будет найден гораздо более эффективный алгоритм
• Сумма и перемножение полиномов, а также подстановка одного в другой в качестве аргумента всё ещё оставляют результат полиномом
• Это свойство удобно при комбинировании алгоритмов

Почему именно полином

• Наконец, смена модели вычислителя всегда оставляет полиномиальный алгоритм полиномиальным (если не учитывать квантовые вычисления)
• Т.е. задача, решаемая за полиномиальное время на обычном ПК (более формально — машине с произвольным доступом к памяти), может быть за полиномиальное время решена и на машине Тьюринга

Класс сложности $NP$

• Класс сложности $NP$ содержит задачи, правильность предоставленного решения которых можно проверить за полиномиальное время
• Т.е. если кто-то уже решил конкретный экземпляр задачи (неважно, сколько времени было на это потрачено), проверить, правильное ли получилось решение, можно за полиномиальное время

Пример задачи из $NP$

• К примеру, существует задача поиска гамильтонова цикла в графе
• Пусть дан граф $G = (V, E)$, нужно определить, есть ли в графе путь, проходящий все вершины ровно по $1$ разу и возвращающийся в исходную вершину

Поиск гамильтонова цикла

• Решить задачу поиска гамильтонова цикла за полиномиальное время на данный момент не представляется возможным
• Однако, если кто-то предоставит решение для конкретного графа в виде последовательности вершин, составляющих гамильтонов цикл, легко проверить, является ли эта последовательность решением

Отношение между $P$ и $NP$

• Очевидно, что все задачи из $P$ также входят в $NP$ (т.е. $P \subseteq NP$)
• Это справедливо, т.к., если решешние задачи можно получить за полиномиальное время, то, чтобы проверить правильность предоставленного решения, можно просто решить задачу заново и сравнить результат

Отношение между $P$ и $NP$

• Однако остаётся открытым вопрос о $P \stackrel{?}{=} NP$
• Несмотря на то, что, чтобы отнести задачу к классу $P$, необходимо только предоставить алгоритм её решения, работающий за полиномиальное время, если такой алгоритм пока что не найден, это не является доказательством того, что задача не входит в $P$

$NP$-полные задачи

• Весомым (но не достаточным для доказательства) аргументом в пользу того, что $P \neq NP$, является существование $NP$-полных задач
• $NP$-полная задача — задача из $NP$, к которой могут быть за полиномиальное время сведены все остальные задачи из $NP$

Сведение

• Сведением называется процесс представления экземпляров одной задачи в качестве экземпляров другой
• Алгоритм сведения должен преобразовывать входы $I_1$ первой задачи $Q_1$ во входы $I_2$ второй задачи $Q_2$ таким образом, чтобы решение $Q_1$ со входом $I_1$ совпадало с решением $Q_2$ со входом $I_2$

Пример сведения

• К примеру, задачу решения линейного уравнения $a_1x + b_1 = 0$ можно свести к задаче решения квадратного уравнения $a_2x^2 + b_2x + c_2 = 0$
• Сделать это можно, положив $a_2 = 0, b_2 = a_1, c_2 = b_1$
• После такого сведения решения квадратного уравнения будут совпадать с решениями линейного

Следствие сводимости

• Пусть задачу $Q_1$ можно свести к задаче $Q_2$ так, что алгоритм сведения будет работать не сложнее, чем решения самих задач
• Из этого следует, что задача $Q_2$ решается не проще, чем задача $Q_1$
• Тогда, если достоверно известно, что $Q_1$ нельзя решить быстрее, чем за некоторое $T(N)$, то и $Q_2$ нельзя решить быстрее, чем за $T(N)$

$NP$-полные задачи

• Таким образом, любую $NP$-полную задачу решить не проще, чем все остальные $NP$-полные задачи, т.к. все они сводятся друг к другу за полиномиальное время
• Более того, если хотя бы для одной $NP$-полной задачи найдётся решение за полиномиальное время, это сразу же даст решение всех остальных $NP$-полных задач за полиномиальное время

Следствие

• Таким образом, чтобы доказать, что для задачи не существует эффективного алгоритма решения, достаточно показать, что к ней сводится хотя бы одна $NP$-полная задача
• Такое сведение будет гарантией отсутствия полиномиального решения этой задачи по крайней мере до тех пор, пока не будет доказано, что $P = NP$

$NP$-сложные задачи

• Следует также отличать отдельный класс $NP$-сложных задач
• В этот класс входят задачи, лежащие за рамками $NP$
• Для таких задач и поиск решения и его верификация работают сложнее, чем за полиномиальное время

Примеры $NP$-полных задач

• Примечательно, что задачи из класса $P$ и $NP$-полные задачи зачастую имеют мало отличий
• Задача поиска кратчайшего пути между вершинами на графе принадлежит к классу $P$, тогда как задача поиска саомго длинного пути — $NP$-полная

Примеры $NP$-полных задач

• Задача поиска эйлерова цикла на графе решается за полиномиальное время, а задача поиска гамильтонова цикла — $NP$-полная
• Задача проверки выполнимости $2-CNF$ решается за полиномиальное время, а задача проверки выполнимости $3-CNF$ — $NP$-полная

Полезные источники

1. RU Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ, 3-е издание. Глава 34.
2. RU С. Скиена. Алгоиртмы. Руководство по разработке. 2-е издание. Глава 9 – Более простое и краткое объяснение.
3. RU А.Левитин. Алгоритмы: введение в разработку и анализ. Глава 10 — ещё один вариант изложения материала

Полезные источники

4. RU Курс видеолекций от преподавателя из МФТИ