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