Класс NP

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

Интуитивно, класс NP содержит задачи, для которых сравнительно легко (за полиномиальное время на детерминированной машине Тьюринга) можно доказать, что потенциальное решение задачи действительно является таковым. Или, что эквивалентно, задачи 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}$.

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

Отношения класса NP с другими классами

Класс NP включает в себя класс P (даже точнее, известно включение $P\subset NP\cap co{-}NP\subset NP$). Однако ничего не известно о строгости этого включения. Задача о равенстве классов P и NP является одной из центральных открытых проблем теории алгоритмов. Если они равны, то любую задачу из класса NP можно будет решить быстро (за полиномиальное время). Однако научное сообщество^[кто?] склоняется в сторону отрицательного ответа на этот вопрос.

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

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

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

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

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

Литература

• Задачи поиска. Классы P и NP. Сведения. NP-полные задачи
• "Введение в структурную теорию сложности". Курс лекций.