Класс NP

В теории алгоритмов классом NP (от англ. non-deterministic polynomial) называют множество проблем разрешимости, решение которых возможно проверить на машине Тьюринга за время, не превосходящее полинома от размера входных данных, при наличии некоторых дополнительных сведений (так называемого сертификата решения).

Эквивалентно класс NP можно определить как содержащий задачи, которые можно за полиномиальное время решить на недетерминированной машине Тьюринга.

Задачи, имеющие полиномиальные по времени алгоритмы решения, можно решать с помощью компьютера значительно быстрее, чем путём прямого перебора, время которого экспоненциально. Это обусловливает практическое значение проблемы о равенстве классов P и NP.

Определения

Класс сложности NP определяется для множества языков, то есть множеств слов над конечным алфавитом $\Sigma$. Язык L называется принадлежащим классу NP, если существуют двуместный предикат $R(x,\,y)$ из класса P (то есть вычислимый за полиномиальное время) и константа $c>0$ такие, что для всякого слова x условие «x принадлежит L» равносильно условию «найдётся y длины меньше $|x|^{c}$ такой, что верно $R(x,\,y)$» (где |x| — длина слова x). Слово y называется сертификатом принадлежности x языку L. Таким образом, если у нас есть слово, принадлежащее языку, и ещё одно слово-свидетель ограниченной длины (которое бывает трудно найти), то мы быстро сможем удостовериться в том, что x действительно принадлежит L.

Эквивалентное определение можно получить, используя понятие недетерминированной машины Тьюринга (то есть такой машины Тьюринга, у программы которой могут существовать разные строки с одинаковой левой частью). Если машина встретила «развилку», то есть неоднозначность в программе, то дальше возможны разные варианты вычисления. Предикат $R(x)$, который представляет данная недетерминированная машина Тьюринга, считается равным единице, если существует хоть один вариант вычисления, возвращающий 1, и нулю, если все варианты возвращают 0. Если длина вычисления, дающего 1, не превосходит некоторого многочлена от длины x, то предикат называется принадлежащим классу NP. Если у языка существует распознающий его предикат из класса NP, то язык называется принадлежащим классу NP. Это определение эквивалентно приведённому выше: в качестве свидетеля можно взять номера нужных веток при развилках в вычислении. Так как для x принадлежащему языку длина всего пути вычисления не превосходит многочлена от длины x, то и длина свидетеля также будет ограничена многочленом от длины x.

Всякую задачу о принадлежности слова x языку L, лежащую в классе NP, можно решить за экспоненциальное время перебором всех возможных сертификатов длины меньше $|x|^{c}$. Для её решения на квантовом компьютере можно использовать GSA. В этом случае общее количество всех возможных сертификатов, которые нужно перебрать, можно определить по формуле суммы $|x|^{c}$ членов геометрической прогрессии со знаменателем, равным числу символов $|\Sigma |$ в алфавите $\Sigma$, и 1-м членом, равным 1:

$N={\frac {1-|\Sigma |^{|x|^{c}}}{1-|\Sigma |}}$

Поэтому для поиска нужного сертификата методом GSA требуется $\left\lceil \log _{2}{\frac {1-|\Sigma |^{|x|^{c}}}{1-|\Sigma |}}\right\rceil$ Q-битов. Сертификат будет найден за время, не превышающее $O\left({\sqrt {\frac {1-|\Sigma |^{|x|^{c}}}{1-|\Sigma |}}}\right)$.

Соотношение с другими классами

Класс языков, дополнения которых принадлежат NP, называется классом co-NP, хотя и не доказано, что этот класс отличен от класса NP. Пересечение классов NP и co-NP содержит класс P. В частности, класс NP включает в себя класс P. Однако ничего не известно о строгости этого включения.

Задача о равенстве классов P и NP является одной из центральных открытых проблем теории алгоритмов. Если они равны, то любую задачу из класса NP можно будет решить быстро (за полиномиальное время). Однако научное сообщество склоняется в сторону отрицательного ответа на этот вопрос.

Класс NP включается в другие, более широкие классы, например, в класс PH. Существуют также открытые вопросы о строгости его включения в другие классы.

Примеры задач класса NP

Можно привести много задач, про которые на сегодняшний день неизвестно, принадлежат ли они P, но известно, что они принадлежат NP. Среди них:

• Задача выполнимости булевых формул: узнать по данной булевой формуле, существует ли набор входящих в неё переменных, обращающий её в 1. Сертификат — такой набор.
• Задача о клике: по данному графу узнать, есть ли в нём клики (полные подграфы) заданного размера. Сертификат — номера вершин, образующих клику.
• Определение наличия в графе гамильтонова цикла. Сертификат — последовательность вершин, образующих гамильтонов цикл.
• Неоптимизационный вариант задачи о коммивояжёре (существует ли маршрут не длиннее, чем заданное значение k) — расширенный и более приближенный к реальности вариант предыдущей задачи. Сертификат - такой маршрут.
• Существование целочисленного решения у заданной системы линейных неравенств. Сертификат — решение.

Среди всех задач класса NP можно выделить «самые сложные» — NP-полные задачи. Если удастся решить любую из них за полиномиальное время, то все задачи класса NP также можно будет решить за полиномиальное время.

См. также

• Оптимизация (математика)
• Равенство классов P и NP

Литература

• Томас Х. Кормен и др. Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: «Вильямс», 2006. — 1296 с. — ISBN 0-07-013151-1.
• Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — 528 с. — ISBN 0-201-44124-1.
• Задачи поиска. Классы P и NP. Сведения. NP-полные задачи
• «Введение в структурную теорию сложности». Курс лекций.