Просмотр кода страницы Класс NP

В [[теория алгоритмов|теории алгоритмов]] '''классом NP''' (от {{lang-en|non-deterministic polynomial}}) называют множество [[Задача разрешимости|задач разрешимости]], решение которых возможно проверить на [[Детерминированная машина Тьюринга|машине Тьюринга]] за время, не превосходящее значения некоторого [[многочлен]]а от размера входных данных, при наличии некоторых дополнительных сведений (так называемого ''сертификата решения'').

Эквивалентно класс NP включает задачи, которые можно за [[Временная сложность алгоритма#Полиномиальное время|полиномиальное время]] решить на [[Недетерминированная машина Тьюринга|недетерминированной машине Тьюринга]].

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

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

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

Всякую задачу о принадлежности слова ''x'' языку ''L'', лежащую в классе NP, можно решить за [[экспоненциальное время]] [[полный перебор|перебором]] всех возможных сертификатов длины меньше <math>|x|^c</math>. Для её решения на [[квантовый компьютер|квантовом компьютере]] можно использовать [[GSA (Алгоритм)|GSA]]. В этом случае общее количество всех возможных сертификатов, которые нужно перебрать, можно определить по формуле [[Геометрическая_прогрессия#Свойства|суммы <math>|x|^c</math> членов геометрической прогрессии]] со [[Дробь (математика)|знаменателем]], равным [[мощность множества|числу символов <math>|\Sigma|</math>]] в алфавите <math>\Sigma</math>, и 1-м членом, равным [[1]]:

<math>N=\frac{1-|\Sigma|^{|x|^c}}{1-|\Sigma|}</math>

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

== Соотношение с другими классами ==
[[Файл:P_np_np-complete_np-hard.svg|thumb|400px|right|Варианты положения класса NP в иерархии классов сложности, в зависимости решения вопроса о [[Равенство классов P и NP|равенстве классов P и NP]].]]
Класс языков, дополнения которых принадлежат NP, называется классом '''co-NP''', хотя и не доказано, что этот класс отличен от класса NP. Пересечение классов NP и co-NP содержит [[класс P]]. В частности, класс NP включает в себя класс P. Однако ничего не известно о строгости этого включения.

Задача о [[равенство классов P и NP|равенстве классов P и NP]] является одной из центральных открытых проблем теории алгоритмов. Если они равны, то любую задачу из класса NP можно будет решить быстро (за полиномиальное время). Однако научное сообщество склоняется в сторону отрицательного ответа на этот вопрос.<ref>{{статья |заглавие=The P=?NP poll. |издание=SIGACT News |том=33 |номер=2 |страницы=34—47 |ссылка=http://www.cs.umd.edu/~gasarch/papers/poll.pdf |doi=10.1145/1052796.1052804 |язык=und |автор=William I. Gasarch |год=2002 |archivedate=2019-10-27 |archiveurl=https://web.archive.org/web/20191027015501/http://www.cs.umd.edu/%7Egasarch/papers/poll.pdf }}</ref>

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

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

Можно привести много задач, про которые на сегодняшний день неизвестно, принадлежат ли они P, но известно, что они принадлежат NP. Среди них:
* [[Задача выполнимости булевых формул]]: узнать по данной [[логика высказываний|булевой формуле]], существует ли набор входящих в неё переменных, обращающий её в 1. Сертификат — такой набор.
* [[Задача о клике]]: по данному [[граф (математика)|графу]] узнать, есть ли в нём ''клики'' (полные подграфы) заданного размера. Сертификат — номера вершин, образующих клику.
* Определение наличия в графе [[гамильтонов цикл|гамильтонова цикла]]. Сертификат — последовательность вершин, образующих гамильтонов цикл.
* Неоптимизационный вариант [[Задача о коммивояжёре|задачи о коммивояжёре]] (существует ли маршрут не длиннее, чем заданное значение k) — расширенный и более приближенный к реальности вариант предыдущей задачи. Сертификат - такой маршрут.
* Существование целочисленного решения у заданной системы линейных неравенств. Сертификат — решение.
*''Отсутствие'' у заданного числа <math>m</math> делителей <math>d</math> таких что <math>1 < d \leq k</math>. Сертификат — разбиение числа <math>m</math> на простые сомножители вместе с их [[Сертификат простоты|сертификатами простоты]].

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

== См. также ==
* [[Оптимизация (математика)]]
* [[Равенство классов P и NP]]

== Примечания ==
{{примечания}}

== Литература ==
* {{книга
|автор = Томас Х. Кормен и др.
|заглавие = Алгоритмы: построение и анализ
|оригинал = Introduction to Algorithms
|ссылка = 
|издание = 2-е изд
|место =  М.
|издательство = [[Вильямс (издательство)|«Вильямс»]]
|год = 2006
|страниц = 1296
|isbn = 0-07-013151-1
}}
* {{книга
|заглавие = Введение в теорию автоматов, языков и вычислений
|оригинал = Introduction to Automata Theory, Languages, and Computation
|автор = [[Джон Хопкрофт]], Раджив Мотвани, Джеффри Ульман
|ссылка = 
|isbn = 0-201-44124-1
|страниц = 528
|год = 2002
|издание = 
|место =  М.
|издательство = [[Вильямс (издательство)|«Вильямс»]]
}}
* [http://logic.pdmi.ras.ru/~hirsch/students/complexity1/lecture1.pdf Задачи поиска. Классы P и NP. Сведения. NP-полные задачи] {{Wayback|url=http://logic.pdmi.ras.ru/~hirsch/students/complexity1/lecture1.pdf |date=20110613052030 }}
* [https://web.archive.org/web/20100923103517/http://www.csin.ru/courses/vvedenie-v-strukturnuyu-teoriyu-slozhnosti «Введение в структурную теорию сложности»]. Курс лекций.

{{rq|refless|isbn}}
{{Классы сложности}}

[[Категория:Классы сложности]]