NP-полнота

Булева проблема выполнимости (SAT) требует определить, может ли пропозициональная формула (изображенный пример) стать истинной путем соответствующего присвоения («решения») значений истинности ее переменным. Хотя легко проверить, делает ли данное присваивание формулу истинной , Неизвестен существенно более быстрый способ найти удовлетворяющее задание, чем попробовать все задания подряд. Кук и Левин доказали, что любую легко проверяемую задачу можно решить так же быстро, как SAT, который, следовательно, является NP-полным.

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

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

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

Точнее, каждому входу задачи должен быть сопоставлен набор решений полиномиальной длины, достоверность каждого из которых можно быстро проверить (за полиномиальное время ), так, что выход для любого входа будет «да», если набор решений непустой, и «нет», если он пуст. Класс сложности задач такой формы называется 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-полноты (статья P = NP )

Проблема с решением $\scriptstyle C$ является NP-полной, если:

1. $\scriptstyle C$ находится в NP, и
2. Любая задача в NP сводится к $\scriptstyle C$ за полиномиальное время.

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

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

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

Фон

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

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

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

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

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

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

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

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

• Проблема булевой выполнимости (SAT)
• Задача о рюкзаке
• Проблема гамильтонового пути
• Задача коммивояжера (вариант решения)
• Проблема изоморфизма подграфов
• Проблема суммы подмножества
• Проблема с щелчком
• Проблема с вершинным покрытием
• Независимая задача множества
• Задача о доминирующем множестве
• Задача о раскраске графа
• Судоку

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

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

Промежуточные проблемы

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

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

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

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

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

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

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

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

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

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

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

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

Другой тип сокращения, который также часто используется для определения NP-полноты, - это сокращение «много-один» в логарифмическом пространстве , которое представляет собой сокращение «многие-один», которое можно вычислить только с логарифмическим объемом пространства. Поскольку каждое вычисление, которое может быть выполнено в логарифмическом пространстве , также может быть выполнено за полиномиальное время, из этого следует, что если существует сокращение «много-один» в логарифмическом пространстве, то существует также сокращение «многие-один» за полиномиальное время. Этот тип сокращения является более точным, чем более обычные сокращения «много-единица» за полиномиальное время, и позволяет нам различать больше классов, таких как P-complete . Вопрос о том, будет ли при таких видах редукций определение NP-полных изменений, остается открытым вопросом. Все известные в настоящее время NP-полные задачи являются NP-полными при сокращении пространства журнала. Все известные в настоящее время NP-полные задачи остаются NP-полными даже при гораздо более слабых редукциях, таких как $AC_{0}$ сокращения и $NC_{0}$ сокращения. Известно, что некоторые NP-полные задачи, такие как SAT, являются полными даже при полилогарифмических временных проекциях. Однако известно, что АС ⁰ сокращения определяют строго меньший класс, чем сокращения за полиномиальное время.

Мы

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

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

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

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

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

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

• союз
• пересечение
• конкатенация
• Клини звезда

Неизвестно, замкнут ли NPC при дополнении , поскольку NPC= со-NPC тогда и только тогда, когда NP= со-NP , и поскольку NP=со-NP — вопрос открытый .

См. также

• Почти завершено
• Гаджет (информатика)
• Теорема Ладнера
• Список NP-полных задач
• NP-жесткий
• P = проблема NP
• Сильно NP-полный
• Коммивояжер (фильм, 2012 г.)

Ссылки

Источники

• Гэри, Майкл Р .; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Серия книг по математическим наукам (1-е изд.). Нью-Йорк: WH Freeman and Company . ISBN  9780716710455 . МР   0519066 . OCLC   247570676 . Эта книга представляет собой классику, в которой развивается теория, а затем каталогизируется множество NP-полных проблем.
• Кук, С.А. (1971). «Сложность процедур доказательства теорем». Труды Третьего ежегодного симпозиума ACM по теории вычислений, ACM, Нью-Йорк . стр. 151–158. дои : 10.1145/800157.805047 .
• Данн, PE «Аннотированный список избранных NP-полных задач» . COMP202, факультет компьютерных наук, Ливерпульский университет . Проверено 21 июня 2008 г.
• Крещенци, П.; Канн, В.; Халлдорссон, М.; Карпински, М .; Вегингер, Г. «Сборник задач оптимизации NP» . КТХ, Стокгольм . Проверено 24 октября 2020 г.
• Дальке, К. «NP-полные задачи» . Справочный проект по математике . Проверено 21 июня 2008 г.
• Карлссон, Р. «Лекция 8: NP-полные задачи» (PDF) . Кафедра компьютерных наук Лундского университета, Швеция. Архивировано из оригинала (PDF) 19 апреля 2009 г. Проверено 21 июня 2008 г.
• Сунь, Х.М. «Теория NP-полноты» . Лаборатория информационной безопасности, факультет компьютерных наук, Национальный университет Цин Хуа , город Синьчжу, Тайвань. Архивировано из оригинала (PPT) 2 сентября 2009 г. Проверено 21 июня 2008 г.
• Цзян Дж.Р. «Теория NP-полноты» (PPT) . Кафедра компьютерных наук и информационной инженерии, Национальный центральный университет , город Джонли, Тайвань . Проверено 21 июня 2008 г.
• Кормен, TH ; Лейзерсон, CE ; Ривест, РЛ ; Штейн, К. (2001). «Глава 34: NP – Полнота». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. стр. 966–1021. ISBN  978-0-262-03293-3 .
• Сипсер, М. (1997). «Разделы 7.4–7.5 (NP-полнота, Дополнительные NP-полные задачи)» . Введение в теорию вычислений . Издательство ПВС. стр. 248–271 . ISBN  978-0-534-94728-6 .
• Пападимитриу, К. (1994). «Глава 9 (NP-полные задачи)». Вычислительная сложность (1-е изд.). Эддисон Уэсли. стр. 181–218. ISBN  978-0-201-53082-7 .
• Вычислительная сложность игр и головоломок
• Тетрис сложно даже приблизительно оценить
• Сапер NP-полный!
• Берн, Маршалл (1990). «Более быстрые точные алгоритмы для деревьев Штейнера в плоских сетях». Сети . 20 (1): 109–120. дои : 10.1002/net.3230200110 . .
• Дейнеко Владимир Георгиевич; Клинц, Беттина; Вегингер, Герхард Дж. (2006). «Точные алгоритмы решения гамильтоновой задачи цикла в плоских графах». Письма об исследованиях операций . 34 (3): 269–274. дои : 10.1016/j.orl.2005.04.013 . .
• Дорн, Фредерик; Пеннинккс, Элко; Бодлендер, Ганс Л .; Фомин, Федор В. (2005). «Эффективные точные алгоритмы на плоских графах: использование разложения ветвей с разрезом по сфере». Учеб. 13-й Европейский симпозиум по алгоритмам (ESA '05) . Конспекты лекций по информатике. Том. 3669. Шпрингер-Верлаг. стр. 95–106. дои : 10.1007/11561071_11 . ISBN  978-3-540-29118-3 . .
• Липтон, Ричард Дж .; Тарьян, Роберт Э. (1980). «Применение теоремы о плоском сепараторе». SIAM Journal по вычислительной технике . 9 (3): 615–627. дои : 10.1137/0209046 . S2CID   12961628 . .

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

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