NP-полнота

В теории вычислительной сложности задача является NP-полной, если:

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

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

Точнее, каждый вход в задачу должен быть связан с набором решений полиномиальной длины, справедливость каждого из которых может быть быстро проверена (за полиномиальное время ), ^[2] таким образом, чтобы выход для любого входа был «да», если набор решений непустой, и «нет», если он пустой. Класс сложности задач такого вида называется NP , сокращение от «недетерминированное полиномиальное время». Задача называется NP-трудной , если все в NP может быть преобразовано в нее за полиномиальное время, даже если она может не быть в NP. Задача является NP-полной, если она одновременно и в NP, и в NP-трудной. NP-полные задачи представляют собой самые сложные задачи в NP. Если некоторая NP-полная задача имеет алгоритм полиномиального времени, то все задачи в NP имеют его. Множество NP-полных задач часто обозначается NP-C или NPC .

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

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

Обзор

NP-полные задачи находятся в NP , множестве всех задач принятия решений , решения которых могут быть проверены за полиномиальное время; NP может быть эквивалентно определено как множество задач принятия решений, которые могут быть решены за полиномиальное время на недетерминированной машине Тьюринга . Задача p в NP является NP-полной, если каждая другая задача в NP может быть преобразована (или сведена) к p за полиномиальное время. ^{[ требуется ссылка ]}

Неизвестно, можно ли быстро решить каждую задачу из NP — это называется проблемой P против NP . Но если любую NP-полную задачу можно решить быстро, то можно решить и любую задачу из NP , потому что определение NP-полной задачи гласит, что каждая задача из NP должна быть быстро сведена к любой NP-полной задаче (то есть ее можно свести за полиномиальное время). Из-за этого часто говорят, что NP-полные задачи сложнее или труднее, чем задачи NP в целом. ^{[ требуется цитата ]}

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

Задача принятия решения является NP-полной, если: ^[^{необходима ссылка}^] $\scriptstyle C$

$\scriptstyle C$ находится в NP, и
Каждая задача из NP сводится к решению за полиномиальное время. ^[3] $\scriptstyle C$

$\scriptstyle C$ можно показать, что она принадлежит классу NP, показав, что возможное решение может быть проверено за полиномиальное время. $\scriptstyle C$

Обратите внимание, что задача, удовлетворяющая условию 2, называется NP-трудной , независимо от того, удовлетворяет ли она условию 1. ^[4]

Следствием этого определения является то, что если бы у нас был алгоритм с полиномиальным временем (на UTM или любой другой абстрактной машине , эквивалентной Тьюрингу ) для , мы могли бы решить все задачи из NP за полиномиальное время. $\scriptstyle C$

Фон

Понятие NP-полноты было введено в 1971 году (см. теорему Кука–Левина ), хотя термин NP-полный был введен позже. На конференции STOC 1971 года между специалистами по информатике разгорелись ожесточенные дебаты о том, можно ли решить NP-полные задачи за полиномиальное время на детерминированной машине Тьюринга . Джон Хопкрофт привел всех на конференции к консенсусу, что вопрос о том, разрешимы ли NP-полные задачи за полиномиальное время, следует отложить на более позднее время, поскольку ни у кого не было никаких формальных доказательств своих утверждений так или иначе. ^{[ требуется цитата ]} Это известно как «вопрос о том, P=NP».

Никто пока не смог окончательно определить, действительно ли NP-полные задачи решаемы за полиномиальное время, что делает это одной из величайших нерешенных проблем математики . Математический институт Клэя предлагает награду в 1 миллион долларов США ( Премия тысячелетия ) любому, кто предоставит формальное доказательство того, что P=NP или P≠NP. ^[5]

Существование NP-полных задач не очевидно. Теорема Кука–Левина утверждает, что проблема булевой выполнимости является NP-полной, тем самым устанавливая, что такие задачи существуют. В 1972 году Ричард Карп доказал, что несколько других задач также являются NP-полными (см. 21 NP-полную задачу Карпа ); таким образом, существует класс NP-полных задач (помимо проблемы булевой выполнимости). После получения первоначальных результатов было показано, что тысячи других задач являются NP-полными путем сведения других задач, ранее показанных как NP-полные; многие из этих задач собраны в Garey & Johnson (1979).

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

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

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

Часто существует лишь небольшая разница между задачей в P и NP-полной задачей. Например, задача 3-выполнимости , ограничение задачи булевой выполнимости, остается NP-полной, тогда как немного более ограниченная задача 2-выполнимости находится в P (в частности, она является NL-полной ), но немного более общая задача max. 2-sat. снова является NP-полной. Определение того, можно ли раскрасить граф в 2 цвета, находится в P, но с 3 цветами является NP-полной, даже если ограничено планарными графами . Определение того, является ли граф циклом или двудольным , очень просто (в L ), но нахождение максимального двудольного или максимального циклического подграфа является NP-полным. Решение задачи о рюкзаке в пределах любого фиксированного процента от оптимального решения может быть вычислено за полиномиальное время, но нахождение оптимального решения является NP-полным.

Промежуточные задачи

Интересным примером является проблема изоморфизма графов , проблема теории графов , определяющая, существует ли изоморфизм графов между двумя графами. Два графа являются изоморфными, если один может быть преобразован в другой простым переименованием вершин . Рассмотрим эти две проблемы:

Изоморфизм графов: Изоморфен ли граф G ₁ графу G ₂ ?
Изоморфизм подграфов: Изоморфен ли граф G ₁ подграфу графа G ₂ ?

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

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

В настоящее время все известные алгоритмы для NP-полных задач требуют времени, которое является суперполиномиальным по размеру входных данных. Задача о вершинном покрытии имеет ^[6] для некоторых и неизвестно, существуют ли более быстрые алгоритмы. $O(1.2738^{k}+nk)$ $к>0$

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

Аппроксимация : вместо поиска оптимального решения ищите решение, которое отличается от оптимального не более чем на один фактор.
Рандомизация : используйте случайность, чтобы получить более быстрое среднее время выполнения , и позвольте алгоритму потерпеть неудачу с некоторой малой вероятностью. Примечание: метод Монте-Карло не является примером эффективного алгоритма в этом конкретном смысле, хотя эволюционные подходы, такие как генетические алгоритмы, могут быть таковыми.
Ограничение: Ограничивая структуру входных данных (например, планарными графами), обычно можно добиться более быстрых алгоритмов.
Параметризация : Часто существуют быстрые алгоритмы, если фиксированы определенные параметры входных данных.
Эвристический : Алгоритм, который работает "достаточно хорошо" во многих случаях, но для которого нет доказательств, что он всегда быстр и всегда дает хороший результат. Часто используются метаэвристические подходы.

Одним из примеров эвристического алгоритма является неоптимальный жадный алгоритм раскраски, используемый для раскраски графа во время фазы выделения регистров некоторых компиляторов, метод, называемый глобальным выделением регистров раскраской графа . Каждая вершина является переменной, ребра рисуются между переменными, которые используются одновременно, а цвета указывают регистр, назначенный каждой переменной. Поскольку большинство машин RISC имеют довольно большое количество регистров общего назначения, даже эвристический подход эффективен для этого приложения. $O(n\log n)$

Полнота при различных типах редукции

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

Другой тип сведения — это полиномиальное сведение по Тьюрингу . Задача является полиномиально-сводимой по Тьюрингу к задаче, если, имея подпрограмму, которая решается за полиномиальное время, можно написать программу, которая вызывает эту подпрограмму и решает ее за полиномиальное время. Это контрастирует со сводимостью «многие-один», которая имеет ограничение, что программа может вызвать подпрограмму только один раз, а возвращаемое значение подпрограммы должно быть возвращаемым значением программы. $\scriptstyle X$ $\scriptstyle Y$ $\scriptstyle Y$ $\scriptstyle X$

Если определить аналог NP-полной задачи с помощью редукций Тьюринга вместо редукций типа «многие-один», то результирующий набор задач не будет меньше NP-полной задачи; открытым остается вопрос, будет ли он больше.

Другой тип редукции, который также часто используется для определения NP-полноты, — это логарифмическая много-однозначная редукция , которая является много-однозначной редукцией, которая может быть вычислена только с логарифмическим количеством пространства. Поскольку каждое вычисление, которое может быть выполнено в логарифмическом пространстве, может быть выполнено и за полиномиальное время, следует, что если существует логарифмическая много-однозначная редукция, то существует и много-однозначная редукция за полиномиальное время. Этот тип редукции более утончен, чем более обычные много-однозначные редукции за полиномиальное время, и он позволяет нам различать больше классов, таких как P-полные . Изменится ли при этих типах редукций определение NP-полных задач, все еще остается открытой проблемой. Все известные в настоящее время NP-полные задачи являются NP-полными при логарифмических редукциях. Все известные в настоящее время NP-полные задачи остаются NP-полными даже при гораздо более слабых редукциях, таких как редукции и редукции. Известно, что некоторые NP-полные задачи, такие как SAT, являются полными даже при полилогарифмических временных проекциях. ^[7] Однако известно, что сокращения AC определяют строго меньший класс, чем сокращения за полиномиальное время. ^[8] $AC_{0}$ $NC_{0}$

Нейминг

Согласно Дональду Кнуту , название «NP-полный» было популяризировано Альфредом Ахо , Джоном Хопкрофтом и Джеффри Ульманом в их знаменитом учебнике «Проектирование и анализ компьютерных алгоритмов». Он сообщает, что они ввели изменение в гранки для книги (с «полиномиально полный») в соответствии с результатами опроса, который он провел среди теоретического сообщества по информатике . ^[9] Другие предложения, высказанные в опросе ^[10], включали « Геркулесов », «грозный», «крутой» Стейглица в честь Кука и аббревиатуру Шэнь Линя «PET», которая означала «вероятно экспоненциальное время», но в зависимости от того, в каком направлении развивалась проблема P против NP , могла означать «доказуемо экспоненциальное время» или «ранее экспоненциальное время». ^[11]

Распространенные заблуждения

Часто встречаются следующие заблуждения. ^[12]

"NP-полные задачи — самые сложные из известных задач". Поскольку NP-полные задачи относятся к NP, время их выполнения не более чем экспоненциально. Однако было доказано, что некоторые задачи требуют больше времени, например, арифметика Пресбургера . Для некоторых задач было даже доказано, что они вообще никогда не могут быть решены, например, проблема остановки .
"NP-полные задачи сложны, потому что существует множество различных решений". С одной стороны, существует множество задач, имеющих столь же большое пространство решений, но которые могут быть решены за полиномиальное время (например, минимальное остовное дерево ). С другой стороны, существуют NP-задачи с максимум одним решением, которые являются NP-трудными при рандомизированном сокращении за полиномиальное время (см. теорему Вэлианта–Вазирани ).
«Решение NP-полных задач требует экспоненциального времени». Во-первых, это означало бы P ≠ NP, что все еще остается нерешенным вопросом. Кроме того, некоторые NP-полные задачи на самом деле имеют алгоритмы, работающие за суперполиномиальное, но субэкспоненциальное время, такое как O(2 ^{√ n} n ). Например, задачи о независимом множестве и доминирующем множестве для планарных графов являются NP-полными, но могут быть решены за субэкспоненциальное время с помощью теоремы о плоском сепараторе . ^[13]
"Каждый случай NP-полной проблемы сложен". Часто некоторые случаи, или даже большинство случаев, могут быть легко решены за полиномиальное время. Однако, если только P=NP, любой алгоритм с полиномиальным временем должен асимптотически быть неверным на более чем полиномиальном числе из экспоненциально множества входных данных определенного размера. ^[14]
"Если P=NP, все криптографические шифры могут быть взломаны". Полиномиальная задача может быть очень трудно решаемой на практике, если степень полинома или константы достаточно велики. Кроме того, информационно-теоретическая безопасность предоставляет криптографические методы, которые невозможно взломать даже при неограниченной вычислительной мощности.
«Крупномасштабный квантовый компьютер мог бы эффективно решать NP-полные задачи». Класс задач принятия решений, которые могут быть эффективно решены (в принципе) отказоустойчивым квантовым компьютером, известен как BQP. Однако считается, что BQP не содержит все NP, а если нет, то он не может содержать ни одну NP-полную задачу. ^[15]

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

Рассматривая задачу принятия решения как формальный язык в некоторой фиксированной кодировке, множество NPC всех NP-полных задач не замкнуто при:

Неизвестно, замкнут ли NPC относительно комплементарности , поскольку NPC = co-NPC тогда и только тогда, когда NP = co-NP , и поскольку NP = co-NP является открытым вопросом . ^[16]

Смотрите также

Ссылки

Цитаты

^ Например, простое присвоение значения true каждой переменной делает 18-й конъюнкт (и, следовательно, всю формулу) ложным . ${\overline {м}}\lor {\overline {р}}\lor {\overline {с}}$
^ Кобэм, Алан (1965). «Внутренняя вычислительная сложность функций». Proc. Логика, методология и философия науки II . Северная Голландия.
^ J. van Leeuwen (1998). Справочник по теоретической информатике . Elsevier. стр. 84. ISBN 978-0-262-72014-4.
^ J. van Leeuwen (1998). Справочник по теоретической информатике . Elsevier. стр. 80. ISBN 978-0-262-72014-4.
^ Кирш, Энди. «Выдающийся математик утверждает, что решил одну из величайших загадок математики — и это одна из 6 задач с призом в 1 миллион долларов». Business Insider . Получено 24.04.2023 .
^ Чэнь, Цзяньэр; Кань, Ияд А.; Ся, Ге (2010-09-06). «Улучшенные верхние границы для покрытия вершин». Теоретическая информатика . 411 (40): 3736–3756. doi : 10.1016/j.tcs.2010.06.026 . ISSN 0304-3975.
^ Агравал, М.; Аллендер, Э.; Рудич, Стивен (1998). «Снижение сложности схем: теорема об изоморфизме и теорема о зазоре». Журнал компьютерных и системных наук . 57 (2): 127–143. doi : 10.1006/jcss.1998.1583 . ISSN 1090-2724.
^ Агравал, М .; Аллендер, Э.; Импальяццо, Р.; Питасси, Т .; Рудич, Стивен (2001). «Уменьшение сложности сокращений». Computational Complexity . 10 (2): 117–138. doi :10.1007/s00037-001-8191-1. ISSN 1016-3328. S2CID 29017219.
↑ Дон Кнут , Трейси Ларраби и Пол М. Робертс, «Математическое письмо». Архивировано 27 августа 2010 г. в Wayback Machine § 25, MAA Notes No. 14 , MAA, 1989 (также Stanford Technical Report, 1987).
^ Кнут, ДФ (1974). «Терминологическое предложение». SIGACT News . 6 (1): 12–18. doi :10.1145/1811129.1811130. S2CID 45313676.
↑ См. опрос или [1] Архивировано 07.06.2011 на Wayback Machine .
^ Болл, Филип (2000). «ДНК-компьютер помогает коммивояжеру». Nature . doi :10.1038/news000113-10.
^ Берн (1990); Дейнеко, Клинц и Вегингер (2006); Дорн и др. (2005); Липтон и Тарьян (1980).
^ Хемаспандра, LA; Уильямс, Р. (2012). "SIGACT News Complexity Theory Column 76". ACM SIGACT News . 43 (4): 70. doi :10.1145/2421119.2421135. S2CID 13367514.
^ Ааронсон, Скотт (2010). «BQP и полиномиальная иерархия». В Шульман, Леонард Дж. (ред.). Труды 42-го симпозиума ACM по теории вычислений, STOC 2010, Кембридж, Массачусетс, США, 5–8 июня 2010 г. Ассоциация вычислительной техники. стр. 141–150. arXiv : 0910.4698 . doi :10.1145/1806689.1806711. ISBN 978-1-4503-0050-6.
^ Тэлбот, Джон; Уэлш, DJA (2006), Сложность и криптография: Введение, Cambridge University Press, стр. 57, ISBN 9780521617710Вопрос о том , равны ли NP и co-NP, вероятно, является второй по важности открытой проблемой в теории сложности после вопроса о соотношении P и NP.

Источники

Garey, Michael R .; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness . Серия книг по математическим наукам (1-е изд.). Нью-Йорк: WH Freeman and Company . ISBN 9780716710455. MR 0519066. OCLC 247570676.Эта книга является классикой, развивающей теорию, а затем каталогизирующей многие NP-полные задачи.
Кук, С.А. (1971). «Сложность процедур доказательства теорем». Труды Третьего ежегодного симпозиума ACM по теории вычислений, ACM, Нью-Йорк . С. 151–158. doi : 10.1145/800157.805047 .
Данн, П.Е. "Аннотированный список избранных NP-полных задач". COMP202, Кафедра компьютерных наук, Ливерпульский университет . Получено 21 июня 2008 г.
Крещенци, П.; Канн, В.; Халлдорссон, М.; Карпински, М .; Вегингер, Г. «Сборник задач оптимизации NP». КТХ, Стокгольм . Проверено 24 октября 2020 г.
Дальке, К. "NP-полные задачи". Проект Math Reference . Получено 21.06.2008 .
Karlsson, R. "Lecture 8: NP-complete problems" (PDF) . Dept. of Computer Science, Lund University, Sweden. Архивировано из оригинала (PDF) 19 апреля 2009 г. . Получено 21 июня 2008 г.
Sun, HM "Теория NP-полноты". Лаборатория информационной безопасности, кафедра компьютерных наук, Национальный университет Цинхуа , город Синьчжу, Тайвань. Архивировано из оригинала (PPT) 2009-09-02 . Получено 2008-06-21 .
Цзян, Дж. Р. "Теория NP-полноты" (PPT) . Кафедра компьютерных наук и информационной инженерии, Национальный центральный университет , город Чжунли, Тайвань . Получено 21 июня 2008 г.
Cormen, TH ; Leiserson, CE ; Rivest, RL ; Stein, C. (2001). "Глава 34: NP–полнота". Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. стр. 966–1021. ISBN 978-0-262-03293-3.
Sipser, M. (1997). "Разделы 7.4–7.5 (NP-полнота, Дополнительные NP-полные задачи)" . Введение в теорию вычислений . PWS Publishing. стр. 248–271. ISBN 978-0-534-94728-6.
Papadimitriou, C. (1994). "Глава 9 (NP-полные задачи)". Computational Complexity (1-е изд.). Addison Wesley. стр. 181–218. ISBN 978-0-201-53082-7.
Вычислительная сложность игр и головоломок
Тетрис — это сложно, даже приблизительно
«Сапер» — NP-полная игра!
Берн, Маршалл (1990). «Более быстрые точные алгоритмы для деревьев Штейнера в плоских сетях». Networks . 20 (1): 109–120. doi :10.1002/net.3230200110..
Дейнеко, Владимир Г.; Клинц, Беттина; Вёгингер, Герхард Дж. (2006). «Точные алгоритмы для задачи о гамильтоновом цикле в планарных графах». Operations Research Letters . 34 (3): 269–274. doi :10.1016/j.orl.2005.04.013..
Dorn, Frederic; Penninkx, Eelko; Bodlaender, Hans L. ; Fomin, Fedor V. (2005). "Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions". Proc. 13th European Symposium on Algorithms (ESA '05) . Lecture Notes in Computer Science. Vol. 3669. Springer-Verlag. pp. 95–106. doi :10.1007/11561071_11. ISBN 978-3-540-29118-3..
Липтон, Ричард Дж .; Тарьян, Роберт Э. (1980). «Применение теоремы о плоском сепараторе». Журнал SIAM по вычислениям . 9 (3): 615–627. doi :10.1137/0209046. S2CID 12961628..

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

Скотт Ааронсон , NP-полные задачи и физическая реальность , ACM SIGACT News, т. 36, № 1. (март 2005 г.), стр. 30–52.
Лэнс Фортнау , Статус проблемы P против NP , Commun. ACM , Vol. 52, No. 9. (2009), стр. 78–86.