Класс NP
В
Эквивалентно класс NP включает задачи, которые можно за полиномиальное время решить на недетерминированной машине Тьюринга.
Задачи, имеющие полиномиальные по времени алгоритмы решения, можно решать с помощью компьютера значительно быстрее, чем путём прямого перебора, время которого экспоненциально. Это обуславливает практическое значение проблемы о равенстве классов P и NP.
Определения
Класс сложности NP определяется для множества языков, то есть множеств слов над конечным алфавитом . Язык L называется принадлежащим классу NP, если существуют двуместный предикат из класса P (то есть вычислимый за полиномиальное время) и константа такие, что для всякого слова x условие «x принадлежит L» равносильно условию «найдётся y длины меньше такой, что верно » (где |x| — длина слова x). Слово y называется сертификатом принадлежности x языку L. Таким образом, если у нас есть слово, принадлежащее языку, и ещё одно слово-свидетель ограниченной длины (которое бывает трудно найти), то мы быстро сможем удостовериться в том, что x действительно принадлежит L.
Эквивалентное определение можно получить, используя понятие недетерминированной машины Тьюринга (то есть такой машины Тьюринга, у программы которой могут существовать разные строки с одинаковой левой частью). Если машина встретила «развилку», то есть неоднозначность в программе, то дальше возможны разные варианты вычисления. Предикат , который представляет данная недетерминированная машина Тьюринга, считается равным единице, если существует хоть один вариант вычисления, возвращающий 1, и нулю, если все варианты возвращают 0. Если длина вычисления, дающего 1, не превосходит некоторого многочлена от длины x, то предикат называется принадлежащим классу NP. Если у языка существует распознающий его предикат из класса NP, то язык называется принадлежащим классу NP. Это определение эквивалентно приведённому выше: в качестве свидетеля можно взять номера нужных веток при развилках в вычислении. Так как для x принадлежащему языку длина всего пути вычисления не превосходит многочлена от длины x, то и длина свидетеля также будет ограничена многочленом от длины x.
Всякую задачу о принадлежности слова x языку L, лежащую в классе NP, можно решить за
Поэтому для поиска нужного сертификата методом GSA требуется
Соотношение с другими классами
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a0/P_np_np-complete_np-hard.svg/400px-P_np_np-complete_np-hard.svg.png)
Класс языков, дополнения которых принадлежат NP, называется классом co-NP, хотя и не доказано, что этот класс отличен от класса NP. Пересечение классов NP и co-NP содержит класс P. В частности, класс NP включает в себя класс P. Однако ничего не известно о строгости этого включения.
Задача о равенстве классов P и NP является одной из центральных открытых проблем теории алгоритмов. Если они равны, то любую задачу из класса NP можно будет решить быстро (за полиномиальное время). Однако научное сообщество склоняется в сторону отрицательного ответа на этот вопрос.[1]
Класс NP включается в другие, более широкие классы, например, в класс PH. Существуют также открытые вопросы о строгости его включения в другие классы.
Примеры задач класса NP
Можно привести много задач, про которые на сегодняшний день неизвестно, принадлежат ли они P, но известно, что они принадлежат NP. Среди них:
- Задача выполнимости булевых формул: узнать по данной булевой формуле, существует ли набор входящих в неё переменных, обращающий её в 1. Сертификат — такой набор.
- Задача о клике: по данному графу узнать, есть ли в нём клики (полные подграфы) заданного размера. Сертификат — номера вершин, образующих клику.
- Определение наличия в графе гамильтонова цикла. Сертификат — последовательность вершин, образующих гамильтонов цикл.
- Неоптимизационный вариант задачи о коммивояжёре(существует ли маршрут не длиннее, чем заданное значение k) — расширенный и более приближенный к реальности вариант предыдущей задачи. Сертификат - такой маршрут.
- Существование целочисленного решения у заданной системы линейных неравенств. Сертификат — решение.
- Отсутствие у заданного числа делителей таких что . Сертификат — разбиение числа на простые сомножители вместе с их сертификатами простоты.
Среди всех задач класса NP можно выделить «самые сложные» — NP-полные задачи. Если удастся решить любую из них за полиномиальное время, то все задачи класса NP также можно будет решить за полиномиальное время.
См. также
Примечания
- 27 октября 2019 года.
Литература
- Томас Х. Кормен и др. Алгоритмы: построение и анализ = 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
- «Введение в структурную теорию сложности». Курс лекций.
Для улучшения этой статьи желательно: |