НП (сложность)

Нерешенная задача в информатике :

${\mathsf {P\ {\overset {?}{=}}\ NP}}$

(еще нерешенные проблемы по информатике)

Диаграмма Эйлера для P , NP-, NP-полного и NP-трудного набора задач. существование проблем внутри NP, но вне P и NP-полноты В предположении, что P ≠ NP, Ладнер установил .

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

• NP — это набор задач, решаемых за полиномиальное время с помощью недетерминированной машины Тьюринга .
• NP — это набор задач решения , проверяемых за полиномиальное время с помощью детерминированной машины Тьюринга .

Первое определение является основой аббревиатуры НП; « недетерминированное полиномиальное время». Эти два определения эквивалентны, поскольку алгоритм, основанный на машине Тьюринга, состоит из двух фаз, первая из которых состоит из предположения о решении, которое генерируется недетерминированным способом, а вторая фаза состоит из детерминированного алгоритма, который проверяет, является ли предположение – это решение проблемы.

Легко видеть, что класс сложности P (все проблемы, решаемые детерминированно за полиномиальное время) содержится в NP (задачи, решения которых можно проверить за полиномиальное время), поскольку если проблема разрешима за полиномиальное время, то решение также поддается проверке за полиномиальное время путем простого решения задачи. Широко распространено мнение, но не доказано, что P меньше, чем NP , другими словами, что существуют проблемы принятия решений, которые не могут быть решены за полиномиальное время, даже если их решения можно проверить за полиномиальное время. Самые сложные задачи в NP называются NP-полными задачами. Алгоритм, решающий такую ​​задачу за полиномиальное время, также способен решить любую другую задачу NP за полиномиальное время. Если бы P на самом деле было равно NP, то существовал бы алгоритм с полиномиальным временем для решения NP-полных и, как следствие, всех NP-задач.

Класс сложности NP связан с классом сложности co-NP , для которого ответ «нет» можно проверить за полиномиальное время. Является ли NP = co-NP — еще один нерешенный вопрос теории сложности.

Формальное определение

Класс сложности NP можно определить в терминах NTIME следующим образом:

${\mathsf {NP}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(n^{k}),$

где ${\mathsf {NTIME}}(n^{k})$ — это набор задач, которые могут быть решены с помощью недетерминированной машины Тьюринга в $O(n^{k})$ время.

В качестве альтернативы NP можно определить с использованием детерминированных машин Тьюринга в качестве верификаторов. Язык L находится в NP тогда и только тогда , когда существуют полиномы p и q и детерминированная машина Тьюринга M такие, что

• Для всех x и y машина M работает за время p (| x |) на входе ⁠ $(x,y)$⁠ .
• Для всех x в L существует строка y длины q (| x |) такая, что ⁠ $M(x,y)=1$⁠ .
• Для всех x не из L и всех строк y длины q (| x |), ⁠ $M(x,y)=0$⁠ .

Фон

Многие проблемы информатики содержатся в NP, например, версии решения многих задач поиска и оптимизации.

Определение на основе верификатора

Чтобы объяснить определение NP на основе верификатора, рассмотрим задачу о сумме подмножества :Предположим, что нам даны некоторые целые числа {−7, −3, −2, 5, 8}, и мы хотим знать, равна ли сумма некоторых из этих целых чисел нулю. Здесь ответ «да», поскольку целые числа {−3, −2, 5} соответствуют сумме (−3) + (−2) + 5 = 0.

Чтобы ответить, дают ли некоторые целые числа ноль, мы можем создать алгоритм, который получает все возможные подмножества. По мере того как количество целых чисел, которые мы вводим в алгоритм, становится больше, количество подмножеств и время вычислений растут экспоненциально.

Но обратите внимание: если нам дано определенное подмножество, мы можем эффективно проверить, равна ли сумма подмножества нулю, суммируя целые числа подмножества. Если сумма равна нулю, это подмножество является доказательством или свидетелем ответа «да». Алгоритм, который проверяет, имеет ли данное подмножество нулевую сумму, является верификатором . Очевидно, что суммирование целых чисел подмножества может быть выполнено за полиномиальное время, и поэтому проблема суммы подмножества находится в NP.

Приведенный выше пример можно обобщить для любой проблемы принятия решений. Учитывая любой случай проблемы $\Pi$ и свидетель W, если существует верификатор V, так что, учитывая упорядоченную пару (I, W) в качестве входных данных, V возвращает «да» за полиномиальное время, если свидетель доказывает, что ответ «да» или «нет» за полиномиальное время иначе, тогда $\Pi$ находится в НП.

Версия этой проблемы с ответом «нет» формулируется следующим образом: «Для любого конечного набора целых чисел имеет ли каждое непустое подмножество ненулевую сумму?». Определение NP на основе верификатора не требует эффективного верификатора для ответов «нет». Класс задач с такими верификаторами для ответов «нет» называется ко-НП. Фактически, остается открытым вопрос, все ли задачи в NP также имеют верификаторы для ответов «нет» и, следовательно, находятся в со-NP.

В некоторой литературе проверяющее лицо называется «сертификатом», а свидетель — « сертификатом ».

Определение машины

Эквивалентом определения, основанного на верификаторе, является следующая характеристика: NP — это класс задач принятия решений , решаемых недетерминированной машиной Тьюринга , работающей за полиномиальное время . То есть проблема решения $\Pi$ находится в NP всякий раз, когда $\Pi$ распознается некоторой недетерминированной машиной Тьюринга с полиномиальным временем $M$ с экзистенциальным условием принятия , означающим, что $w\in \Pi$ тогда и только тогда, когда некоторый путь вычислений $M(w)$ приводит к принимающему состоянию. Это определение эквивалентно определению, основанному на верификаторе, поскольку недетерминированная машина Тьюринга может решить задачу NP за полиномиальное время, недетерминированно выбрав сертификат и запустив верификатор на сертификате. Аналогично, если такая машина существует, то на ее основе естественным образом можно построить верификатор полиномиального времени.

В этом свете мы можем определить co-NP двойственно как класс проблем принятия решений, распознаваемых недетерминированными машинами Тьюринга с полиномиальным временем и экзистенциальным условием отклонения. Поскольку условие экзистенциального отклонения — это то же самое, что и условие универсального принятия , мы можем понимать вопрос NP против со-NP как вопрос, имеют ли условия экзистенциального и универсального принятия одинаковую выразительную силу для класса недетерминированных Тьюринга с полиномиальным временем. машины.

Характеристики

NP замкнут при объединении , пересечении , конкатенации , звезде Клини и развороте . Неизвестно, является ли NP замкнутым относительно дополнения (этот вопрос представляет собой так называемый вопрос «NP против ко-NP»).

Почему некоторые проблемы NP трудно решить

Из-за множества важных проблем этого класса были предприняты обширные усилия по поиску алгоритмов с полиномиальным временем для решения задач NP. Однако в NP остается большое количество задач, которые не поддаются таким попыткам и, по-видимому, требуют суперполиномиального времени . Неразрешимость этих проблем за полиномиальное время является одним из самых больших открытых вопросов в информатике ( Проблема P против NP («P = NP») более подробное обсуждение см. в разделе « ).

Важным понятием в этом контексте является набор NP-полных задач принятия решений, который является подмножеством NP и может быть неофициально описан как «самые сложные» проблемы в NP. Если существует алгоритм с полиномиальным временем хотя бы для одной из них, то существует алгоритм с полиномиальным временем для всех задач в NP. Из-за этого, а также из-за того, что специальные исследования не смогли найти полиномиальный алгоритм для какой-либо NP-полной задачи, как только было доказано, что проблема NP-полна, это широко рассматривается как признак того, что полиномиальный алгоритм для этой задачи маловероятен. существовать.

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

Эквивалентность определений

Два определения NP как класса задач, решаемых недетерминированной машиной Тьюринга (ТМ) за полиномиальное время, и класса задач, проверяемых детерминированной машиной Тьюринга за полиномиальное время, эквивалентны. Доказательство описано во многих учебниках, например, « Введение в теорию вычислений» Сипсера , раздел 7.3.

Чтобы показать это, сначала предположим, что у нас есть детерминированный верификатор. Недетерминированная машина может просто недетерминированно запускать верификатор для всех возможных строк доказательства (для этого требуется только полиномиальное количество шагов, поскольку она может недетерминированно выбирать следующий символ в строке доказательства на каждом шаге, а длина строки доказательства должна быть полиномиально ограничена). ). Если какое-либо доказательство действительно, какой-то путь будет принят; если никакое доказательство не является действительным, строка не соответствует языку и будет отклонена.

И наоборот, предположим, что у нас есть недетерминированная TM под названием A, принимающая заданный язык L. На каждом из полиномиально многих шагов дерево вычислений машины разветвляется не более чем в конечном числе направлений. Должен быть хотя бы один принимающий путь, и строка, описывающая этот путь, является доказательством, передаваемым проверяющему. Затем верификатор может детерминированно моделировать A, следуя только по пути принятия и проверяя, что он принимает в конце. Если A отклоняет входные данные, пути принятия нет, и верификатор всегда будет отклонять.

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

Представление связи между классами сложности

Включения классов сложности, включая P , NP , co-NP , BPP , P/poly , PH и PSPACE.

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

co-NP содержит те задачи, которые не имеют простого доказательства ни для одного случая, иногда называемые контрпримерами. Например, проверка простоты тривиально заключается в co-NP, поскольку можно опровергнуть простоту целого числа, просто указав нетривиальный множитель. NP и co-NP вместе образуют первый уровень в полиномиальной иерархии , выше только P.

NP определяется с использованием только детерминированных машин. Если мы позволим верификатору быть вероятностным (однако это не обязательно машина BPP ), мы получаем класс MA , решаемый с использованием протокола Артура-Мерлина без связи между Артуром и Мерлином.

Связь между BPP и NP неизвестна: неизвестно, является ли NP подмножеством , NP BPP является подмножеством BPP или нет. Если NP содержится в BPP , что считается маловероятным, поскольку это предполагает практические решения для NP-полных задач, то NP = RP и PH ⊆ BPP .

NP — класс проблем принятия решений ; аналогичный класс функциональных задач — FNP .

Единственные известные строгие включения происходят из теоремы об иерархии времени и теоремы об иерархии пространства , и соответственно они ${\mathsf {NP\subsetneq NEXPTIME}}$ и ${\mathsf {NP\subsetneq EXPSPACE}}$.

Другие характеристики

С точки зрения дескриптивной теории сложности NP точно соответствует множеству языков, определяемых экзистенциальной логикой второго порядка ( теорема Феджина ).

NP можно рассматривать как очень простой тип интерактивной системы доказательства , где доказывающая сторона выдает сертификат доказательства, а проверяющий представляет собой детерминированную машину с полиномиальным временем, которая его проверяет. Он является полным, потому что правильная строка доказательства позволит его принять, если таковая имеется, и это правильно, потому что проверяющий не может принять, если нет приемлемой строки доказательства.

Главный результат теории сложности состоит в том, что NP можно охарактеризовать как проблемы, решаемые с помощью вероятностно проверяемых доказательств , где проверяющий использует случайные биты O(log n ) и проверяет только постоянное число битов строки доказательства (класс PCP (log n) , 1)). Говоря более неформально, это означает, что описанный выше NP-верификатор можно заменить на тот, который просто «выборочно проверяет» несколько мест в строке доказательства, а использование ограниченного количества подбрасываний монеты может определить правильный ответ с высокой вероятностью. несколько результатов о сложности аппроксимирующих алгоритмов Это позволяет доказать .

Примеры

П

Все задачи в P обозначаются ${\mathsf {P\subseteq NP}}$. Имея сертификат для проблемы в P , мы можем игнорировать сертификат и просто решить проблему за полиномиальное время.

Целочисленная факторизация

Версия проблемы решения проблемы целочисленной факторизации : для заданных целых чисел n и k существует ли множитель f с 1 < f < k и f , делящий n ?

NP-полные задачи

Основная статья: Список NP-полных задач

Любая NP-полная задача находится в NP.

Булева выполнимость

Проблема булевой выполнимости ( SAT ), в которой мы хотим узнать, верна ли определенная формула в логике высказываний с логическими переменными для некоторого значения переменных.

Коммивояжер

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

Доказательством может быть просто список городов. Тогда проверка, очевидно, может быть выполнена за полиномиальное время. Он просто добавляет элементы матрицы, соответствующие путям между городами.

Недетерминированная машина Тьюринга может найти такой маршрут следующим образом:

• В каждом посещенном городе он будет «угадывать» следующий город, который нужно посетить, пока не посетит каждую вершину. Если он застрянет, он немедленно остановится.
• В конце он проверяет, что пройденный маршрут стоил меньше k за время O ( n ).

Каждое предположение можно рассматривать как « разветвление » новой копии машины Тьюринга для следования по каждому из возможных путей вперед, и если хотя бы одна машина находит маршрут на расстоянии меньше k , эта машина принимает входные данные. (Точно это можно представить как единственную машину Тьюринга, которая всегда делает правильные предположения)

Бинарный поиск в диапазоне возможных расстояний может преобразовать версию решения Коммивояжера в версию оптимизации путем многократного вызова версии решения (полиномиальное количество раз).

Изоморфизм подграфов

Проблема изоморфизма подграфов : определение того, содержит ли граф G изоморфный графу H. подграф ,

См. также

• Машина Тьюринга - вычислительная модель, определяющая абстрактную машину.

Дальнейшее чтение

• Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стейн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN   0-262-03293-7 . Раздел 34.2: Проверка за полиномиальное время, стр. 979–983.
• Майкл Сипсер (1997). Введение в теорию вычислений . Издательство ПВС. ISBN  0-534-94728-Х . Разделы 7.3–7.5 (Класс NP, NP-полнота, Дополнительные NP-полные задачи), стр. 241–271.
• Дэвид Харел , Ишай Фельдман . Алгоритмика: дух вычислений, Аддисон-Уэсли, Ридинг, Массачусетс, 3-е издание, 2004 г.

Внешние ссылки

• Зоопарк сложности : НП
• Американский ученый, посвященный традиционным и новейшим исследованиям теории сложности: «Случайные алгоритмы».