Класс NP

Класс NP

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

Эквивалентно класс 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. Для её решения на квантовом компьютере можно использовать GSA. В этом случае общее количество всех возможных сертификатов, которые нужно перебрать, можно определить по формуле суммы |x|^c членов геометрической прогрессии со знаменателем, равным числу символов |\Sigma| в алфавите \Sigma, и 1-м членом, равным 1:

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

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

Соотношение с другими классами

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

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

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

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

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

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

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

См. также

Примечания

  1. William I. Gasarch (2002). «The P=?NP poll.». SIGACT News 33 (2): 34–47. DOI:10.1145/1052796.1052804.

Литература



Wikimedia Foundation. 2010.

Поможем решить контрольную работу

Полезное


Смотреть что такое "Класс NP" в других словарях:

  • класс — класс, а …   Русский орфографический словарь

  • класс — класс/ …   Морфемно-орфографический словарь

  • КЛАСС — (в логике и математике) 1) понятие, присущее всем элементам некоторой совокупности объектов; 2) совокупность выделенных по некоторому признаку объектов, мыслимая как целое. Понятие К. (множества) обычно относят к числу простейших, неопределяемых… …   Философская энциклопедия

  • Класс! — Класс! …   Википедия

  • КЛАСС — (лат. classis порядок.). 1) разряд однородных предметов. 2) собрание учеников для учебных занятий, а также помещение и самое время, назначенное для урока. 3) степень в государственной службе. Словарь иностранных слов, вошедших в состав русского… …   Словарь иностранных слов русского языка

  • класс — сущ., м., употр. часто Морфология: (нет) чего? класса, чему? классу, (вижу) что? класс, чем? классом, о чём? о классе; мн. что? классы, (нет) чего? классов, чему? классам, (вижу) что? классы, чем? классами, о чём? о классах 1. Классом называют… …   Толковый словарь Дмитриева

  • КЛАСС — КЛАСС, [ас] класса, м. [латин. classis]. 1. Социальная группа, часть общества, объединенная общностью интересов вследствие одинакового отношения к средствам производства и противостоящая другим социальным группам в силу противоположности… …   Толковый словарь Ушакова

  • КЛАСС! — КЛАСС! …   Википедия

  • КЛАСС — (class) Оксфордский словарь английского языка дает следующее определение класса: Разделение общества или порядок в обществе согласно статусу; разряд, категория общества . Но это определение класса столь же разъясняет, сколь и вносит путаницу.… …   Политология. Словарь.

  • класс — а; м. [от лат. classis разряд] 1. (чего) В научной терминологии: совокупность, группа предметов или явлений с общими признаками; разряд, категория. К. млекопитающих. К. земноводных. К. двудольных растений. Плавать на судах различных классов.… …   Энциклопедический словарь

  • класс — См. разряд …   Словарь синонимов

Книги

Другие книги по запросу «Класс NP» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»