В теории сложности вычислений задача является 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-полной , если :
можно показать, что она находится в NP, продемонстрировав, что возможное решение может быть проверено за полиномиальное время.
Обратите внимание, что задача, удовлетворяющая условию 2, называется NP-трудной независимо от того, удовлетворяет ли она условию 1. [4]
Следствием этого определения является то, что если бы у нас был алгоритм с полиномиальным временем (на UTM или любой другой абстрактной машине , эквивалентной Тьюрингу ) для , мы могли бы решить все проблемы в NP за полиномиальное время.
Понятие 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-полными; многие из этих проблем собраны в работе Гари и Джонсона (1979).
Самый простой способ доказать, что какая-то новая задача является NP-полной, — это сначала доказать, что она находится в NP, а затем свести к ней некоторую известную NP-полную задачу. Поэтому полезно знать разнообразные NP-полные задачи. В приведенном ниже списке содержатся некоторые хорошо известные проблемы, которые являются NP-полными, если их выразить как проблемы решения.
Справа представлена диаграмма некоторых задач и редукций , обычно используемых для доказательства их NP-полноты. На этой диаграмме проблемы сведены снизу вверх. Обратите внимание, что эта диаграмма вводит в заблуждение как описание математической взаимосвязи между этими проблемами, поскольку между любыми двумя NP-полными задачами существует полиномиальное сокращение времени ; но это указывает на то, где продемонстрировать это полиномиальное сокращение времени было проще всего.
Часто между задачей P и NP-полной задачей существует лишь небольшая разница. Например, проблема 3-выполнимости , ограничение булевой проблемы выполнимости, остается NP-полной, тогда как немного более ограниченная проблема 2-выполнимости находится в P (в частности, она NL-полна ), но немного более общая задача max . 2-сб. проблема снова NP-полна. Определение того, можно ли раскрасить граф в 2 цвета, находится в P, но в 3 цвета является NP-полным, даже если оно ограничено плоскими графами . Определить, является ли граф циклом или двудольным , очень легко (в L ), но найти максимальный двудольный или максимальный подграф цикла NP-полно. Решение задачи о рюкзаке в пределах любого фиксированного процента оптимального решения может быть вычислено за полиномиальное время, но поиск оптимального решения является NP-полным.
Интересным примером является проблема изоморфизма графов , проблема теории графов , позволяющая определить, существует ли изоморфизм графов между двумя графами. Два графа изоморфны , если один можно преобразовать в другой простым переименованием вершин . Рассмотрим эти две проблемы:
Проблема изоморфизма подграфов NP-полна. Предполагается, что проблема изоморфизма графов не является ни P, ни NP-полной, хотя она существует в NP. Это пример задачи, которая считается сложной , но не считается NP-полной. Этот класс называется NP-промежуточными задачами и существует тогда и только тогда, когда P≠NP.
В настоящее время все известные алгоритмы решения NP-полных задач требуют времени, суперполиномиального по размеру входных данных. Проблема вершинного покрытия имеет [6] для некоторых , и неизвестно, существуют ли более быстрые алгоритмы.
Следующие методы могут быть применены для решения вычислительных задач в целом, и они часто приводят к существенно более быстрым алгоритмам:
Одним из примеров эвристического алгоритма является субоптимальный алгоритм жадной окраски, используемый для раскраски графов на этапе выделения регистров некоторых компиляторов, метод, называемый глобальным распределением регистров раскраски графов . Каждая вершина является переменной, ребра рисуются между переменными, которые используются одновременно, а цвета указывают регистр, присвоенный каждой переменной. Поскольку большинство RISC- машин имеют довольно большое количество регистров общего назначения, для этого приложения эффективен даже эвристический подход.
В приведенном выше определении NP-полноты термин редукция использовался в техническом значении редукции «много-один» за полиномиальное время .
Другой тип сокращения — это сокращение Тьюринга за полиномиальное время. Задача сводится к задаче по Тьюрингу за полиномиальное время, если для заданной подпрограммы, которая решается за полиномиальное время, можно написать программу, которая вызывает эту подпрограмму и решает за полиномиальное время. Это контрастирует со сводимостью «многие к одному», которая имеет ограничение: программа может вызвать подпрограмму только один раз, а возвращаемое значение подпрограммы должно быть возвращаемым значением программы.
Если определить аналог NP-полного с сокращениями Тьюринга вместо сокращений «многие единицы», результирующий набор задач не будет меньше, чем NP-полный; будет ли он больше, вопрос открытый.
Другой тип сокращения, который также часто используется для определения NP-полноты, - это сокращение «многие к одному» в логарифмическом пространстве , которое представляет собой сокращение «многие к одному», которое можно вычислить, используя только логарифмический объем пространства. Поскольку каждое вычисление, которое может быть выполнено в логарифмическом пространстве, также может быть выполнено за полиномиальное время, из этого следует, что если существует сокращение «много-один» в логарифмическом пространстве, то существует также сокращение «многие-один» за полиномиальное время. Этот тип сокращения является более точным, чем более обычные сокращения «много-единица» за полиномиальное время, и позволяет нам различать больше классов, таких как P-complete . Вопрос о том, будет ли при таких видах редукций определение NP-полных изменений, остается открытым вопросом. Все известные в настоящее время NP-полные задачи являются NP-полными при сокращении пространства журнала. Все известные на данный момент NP-полные задачи остаются NP-полными даже при гораздо более слабых редукциях, таких как редукции и редукции. Известно, что некоторые NP-полные задачи, такие как SAT, являются полными даже при полилогарифмических временных проекциях. [7] Однако известно, что сокращения AC определяют строго меньший класс, чем сокращения за полиномиальное время. [8]
По словам Дональда Кнута , название «NP-полный» было популяризировано Альфредом Ахо , Джоном Хопкрофтом и Джеффри Уллманом в их знаменитом учебнике «Проектирование и анализ компьютерных алгоритмов». Он сообщает, что они внесли изменение в гранки книги (с «полиномиально-полных») в соответствии с результатами проведенного им опроса сообщества теоретической информатики . [9] Другие предложения, сделанные в опросе [10] включали « Геркулесов », «грозный», «крутой» Стейглица в честь Кука и аббревиатуру Шэнь Линя «ПЭТ», что означало «вероятно, экспоненциальное время» . , но в зависимости от того, по какому пути пошла проблема P и NP , может означать «доказуемо экспоненциальное время» или «ранее экспоненциальное время». [11]
Часто встречаются следующие заблуждения. [12]
Если рассматривать проблему решения как формальный язык в некоторой фиксированной кодировке, множество NPC всех NP-полных задач не замкнуто при:
Неизвестно, замкнут ли NPC при дополнении , поскольку NPC= со-NPC тогда и только тогда, когда NP= со-NP , и поскольку NP=со-NP — вопрос открытый . [16]
Вопрос о том, равны ли NP и co-NP, вероятно, является второй по важности открытой проблемой в теории сложности после вопроса P и NP.