Класс NP

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

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

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

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

Поэтому для поиска нужного сертификата методом GSA требуется ${\displaystyle \left\lceil \log _{2}{\frac {1-|\Sigma |^{|x|^{c}}}{1-|\Sigma |}}\right\rceil }$ Q-битов. Сертификат будет найден за время, не превышающее ${\displaystyle 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 можно будет решить быстро (за полиномиальное время). Однако научное сообщество склоняется в сторону отрицательного ответа на этот вопрос.[1]

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

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

• Задача выполнимости булевых формул: узнать по данной булевой формуле, существует ли набор входящих в неё переменных, обращающий её в 1. Сертификат — такой набор.
• Задача о клике: по данному графу узнать, есть ли в нём клики (полные подграфы) заданного размера. Сертификат — номера вершин, образующих клику.
• Определение наличия в графе гамильтонова цикла. Сертификат — последовательность вершин, образующих гамильтонов цикл.
• Неоптимизационный вариант задачи о коммивояжёре (существует ли маршрут не длиннее, чем заданное значение k) — расширенный и более приближенный к реальности вариант предыдущей задачи. Сертификат - такой маршрут.
• Существование целочисленного решения у заданной системы линейных неравенств. Сертификат — решение.
• Отсутствие у заданного числа ${\displaystyle m}$ делителей ${\displaystyle d}$ таких что ${\displaystyle 1<d\leq k}$. Сертификат — разбиение числа ${\displaystyle 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-полные задачи
• «Введение в структурную теорию сложности». Курс лекций.