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

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

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

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

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

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

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

Легко видеть, что класс сложности P (все проблемы, решаемые детерминированно за полиномиальное время) содержится в NP (задачи, решения которых можно проверить за полиномиальное время), поскольку если проблема разрешима за полиномиальное время, то решение также можно проверить за полиномиальное время, просто решив задачу. Но НП содержит гораздо больше проблем, ^{[Заметка 2]}самые сложные из них называются NP-полными задачами. Алгоритм, решающий такую задачу за полиномиальное время, также способен решить любую другую задачу NP за полиномиальное время. Самая важная проблема P и NP («P = NP?») спрашивает, существуют ли алгоритмы с полиномиальным временем для решения NP-полных и, как следствие, всех NP-задач. Широко распространено мнение, что это не так. ^[4]

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

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

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

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

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

В качестве альтернативы NP можно определить с использованием детерминированных машин Тьюринга в качестве верификаторов. Язык находится в NP тогда и только тогда , L когда существуют полиномы 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.

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

Определение машины [ править ]

Эквивалентом определения, основанного на верификаторе, является следующая характеристика: 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 ^[6]), мы получаем класс MA , решаемый с использованием протокола Артура-Мерлина без связи между Артуром и Мерлином.

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

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 ? ^[8]

NP-полные задачи [ править ]

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

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

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

Коммивояжер [ править ]

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

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

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

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

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

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

Изоморфизм подграфов [ править ]

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

См. также [ править ]

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

Примечания [ править ]

^ Полиномиальное время показывает, насколько быстро растет количество операций, необходимых алгоритму, относительно размера проблемы. Следовательно, это мера эффективности алгоритма.
^ В предположении, что P ≠ NP.

Ссылки [ править ]

^ Ладнер, Р.Э. (1975). «О структуре полиномиальной приводимости по времени» . Дж. АКМ . 22 : 151–171. дои : 10.1145/321864.321877 . S2CID 14352974 . Следствие 1.1.
^ Перейти обратно: ^а ^б Кляйнберг, Джон; Тардос, Ева (2006). Разработка алгоритмов (2-е изд.). Аддисон-Уэсли. п. 464 . ISBN 0-321-37291-3 .
^ Алсувайель, М.Х.: Алгоритмы: методы проектирования и анализ , стр. 283 .
^ Уильям Гасарч (июнь 2002 г.). «Опрос P=?NP» (PDF) . Новости СИГАКТ . 33 (2): 34–47. дои : 10.1145/1052796.1052804 . S2CID 18759797 . Проверено 29 декабря 2008 г.
^ Кляйнберг, Джон; Тардос, Ева (2006). Разработка алгоритмов (2-е изд.). п. 496 . ISBN 0-321-37291-3 .
^ «Зоопарк сложности:Е» . Зоопарк «Комплекс» . Архивировано из оригинала 11 ноября 2020 г. Проверено 23 марта 2018 г.
^ Лэнс Фортноу, Вытягивание квантовости , 20 декабря 2005 г.
^ Перейти обратно: ^а ^б Вигдерсон, Ави. «P, NP и математика – взгляд на сложность вычислений» (PDF) . Проверено 13 апреля 2021 г.
^ Карп, Ричард (1972). «Сводимость комбинаторных задач» (PDF) . Сложность компьютерных вычислений . стр. 85–103. дои : 10.1007/978-1-4684-2001-2_9 . ISBN 978-1-4684-2003-6 .
^ Ааронсон, Скотт. «P=? NP» (PDF) . Проверено 13 апреля 2021 г.
^ Гэри, Майкл Р.; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . У. Х. Фриман. ISBN 0-7167-1045-5 .

Дальнейшее чтение [ править ]

Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стейн . Введение в алгоритмы , второе издание. 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 г.

Внешние ссылки [ править ]

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

[3] Полиномиальное время показывает, насколько быстро растет количество операций, необходимых алгоритму, относительно размера проблемы. Следовательно, это мера эффективности алгоритма.

[5] В предположении, что P ≠ NP.

[1] Ладнер, Р.Э. (1975). «О структуре полиномиальной приводимости по времени» . Дж. АКМ . 22 : 151–171. дои : 10.1145/321864.321877 . S2CID 14352974 . Следствие 1.1.

[kleinberg2006-2] Перейти обратно: ^а ^б Кляйнберг, Джон; Тардос, Ева (2006). Разработка алгоритмов (2-е изд.). Аддисон-Уэсли. п. 464 . ISBN 0-321-37291-3 .

[4] Алсувайель, М.Х.: Алгоритмы: методы проектирования и анализ , стр. 283 .

[poll-6] Уильям Гасарч (июнь 2002 г.). «Опрос P=?NP» (PDF) . Новости СИГАКТ . 33 (2): 34–47. дои : 10.1145/1052796.1052804 . S2CID 18759797 . Проверено 29 декабря 2008 г.

[kleinberg2006p496-7] Кляйнберг, Джон; Тардос, Ева (2006). Разработка алгоритмов (2-е изд.). п. 496 . ISBN 0-321-37291-3 .

[8] «Зоопарк сложности:Е» . Зоопарк «Комплекс» . Архивировано из оригинала 11 ноября 2020 г. Проверено 23 марта 2018 г.

[9] Лэнс Фортноу, Вытягивание квантовости , 20 декабря 2005 г.

[:0-10] Перейти обратно: ^а ^б Вигдерсон, Ави. «P, NP и математика – взгляд на сложность вычислений» (PDF) . Проверено 13 апреля 2021 г.

[11] Карп, Ричард (1972). «Сводимость комбинаторных задач» (PDF) . Сложность компьютерных вычислений . стр. 85–103. дои : 10.1007/978-1-4684-2001-2_9 . ISBN 978-1-4684-2003-6 .

[12] Ааронсон, Скотт. «P=? NP» (PDF) . Проверено 13 апреля 2021 г.

[13] Гэри, Майкл Р.; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . У. Х. Фриман. ISBN 0-7167-1045-5 .

[1]

[2]

[Примечание 1]

[3]

[Заметка 2]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

v т Это Классы сложности
Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL FL NL NL-complete NC SC CC P P-complete ZPP RP BPP BQP APX FP
Suspected infeasible	UP NP NP-complete NP-hard co-NP co-NP-complete TFNP FNP AM QMA PH ⊕P PP #P #P-complete IP PSPACE PSPACE-complete
Considered infeasible	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY PR R RE ALL
Class hierarchies	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetical hierarchy Boolean hierarchy
Families of classes	DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system
List of complexity classes