Класс NP

Материал из Википедии — свободной энциклопедии

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

[править] Формальное определение

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

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

Всякую задачу, принадлежащую NP, можно решить за экспоненциальное время (перебором всех возможных свидетелей длины меньше n^c).

Легко видеть, что множество языков из NP не замкнуто относительно дополнения. Класс языков, дополнение которых принадлежит NP, называется классом co-NP.

[править] Отношения класса NP с другими классами

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

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

[править] Примеры задач класса NP

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

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

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