NP (сложность)

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

Нерешенная проблема в информатике :

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

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

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

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

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

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

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

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

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

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

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

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

Многие задачи компьютерной науки содержатся в NP, например, версии решений многих задач поиска и оптимизации.

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

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

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

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

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

В некоторой литературе верификатор называется «сертификатором», а свидетель — « сертификатом ». ^[2]

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

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

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

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

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

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

Два определения NP как класса задач, решаемых недетерминированной машиной Тьюринга (TM) за полиномиальное время, и класса задач, проверяемых детерминированной машиной Тьюринга за полиномиальное время, эквивалентны. Доказательство описано во многих учебниках, например, Sipser's Introduction to the Theory of Computation , раздел 7.3.

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

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

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

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

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

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

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

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

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

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

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

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

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

Каждая NP-полная задача входит в NP.

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

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

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

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

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

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

Двоичный поиск в диапазоне возможных расстояний может преобразовать версию решения коммивояжера в версию оптимизации, вызывая версию решения повторно (полиномиальное число раз). ^{[10] [8]}

Задача изоморфизма подграфов заключается в определении того, содержит ли граф G подграф, изоморфный графу H. ^[11 ]

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

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

• Зоопарк сложности : NP
• Учебник American Scientist по традиционным и современным исследованиям теории сложности: «Случайные алгоритмы»