Класс NP

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

Множество задач класса NP включает множество задач класса P (P-задач) — задач, которые можно решить за полиномиальное время на недетерминированной машине Тьюринга.

Время решения P-задач компьютером меньше времени решения задач путём прямого перебора, время которого экспоненциально. Это обуславливает практическую важность доказательства или опровержения гипотезы о том, что множество 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 в иерархии классов сложности, в зависимости решения вопроса о равенстве классов P и NP.

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

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

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

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

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

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

Среди всех задач класса 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-полные задачи Архивная копия от 13 июня 2011 на Wayback Machine
• «Введение в структурную теорию сложности». Курс лекций.