NP-полнота

редактировать

Класс сложности

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

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

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

Точнее, каждый вход проблемы должен быть связан с набором решений полиномиальной длины, достоверность которых можно быстро проверить (за полиномиальное время ), таким образом, чтобы выход для любого входа был "да", если решение установлено непусто и "нет", если я t пусто. Класс сложности задач этой формы называется NP, сокращение от «недетерминированное полиномиальное время». Проблема называется NP-сложной, если все в NP может быть преобразовано в нее за полиномиальное время, даже если это не может быть в NP. И наоборот, проблема NP-полная, если она одновременно NP и NP-трудна. NP-полные задачи представляют собой самые сложные проблемы в NP. Если любая NP-полная задача имеет алгоритм с полиномиальным временем, то все задачи в NP имеют. Набор NP-полных проблем часто обозначается NP-C или NPC .

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

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

Содержание

1 Обзор
2 Формальное определение
3 Предпосылки
4 NP-полное задачи
5 Решение NP-полных задач
6 Полнота при различных типах редукции
7 Именование
8 Распространенные заблуждения
9 Свойства
10 См. также
11 Ссылки
- 11.1 Цитаты
- 11.2 Источники
12 Дополнительная литература

Обзор

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

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

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

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

$C {\ displaystyle \ scriptstyle C }$ $\ scriptstyle C$ находится в NP, и
Каждая проблема в NP сводится к $C {\ displaystyle \ scriptstyle C}$ $\ scriptstyle C$ в полиноме время.

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

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

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

Предпосылки

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

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

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

NP-полные проблемы

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

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

Изоморфизм графа: Изоморфен ли граф G 1 графу G 2?
Изоморфизм подграфа: Изоморфен ли граф G 1 подграфу графа G 2?

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

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

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

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

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

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

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

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

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

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

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

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

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

Другой тип редукции, который также часто используется для определения NP-полноты, - это логарифмическое сокращение «многие-единицы», которое представляет собой редукцию «многие-единицы», которую можно вычислить только с помощью логарифмической количество места. Так как каждое вычисление, которое может быть выполнено в логарифмическом пространстве, также может быть выполнено за полиномиальное время, из этого следует, что если есть сокращение "многие-единицы" в логарифмическом пространстве, то существует также сокращение "многие-единицы" за полиномиальное время. Этот тип редукции более тонок, чем более обычное полиномиальное сокращение «много-один», и позволяет нам различать больше классов, таких как P-complete. Вопрос о том, является ли определение NP-полных изменений при этих типах редукций открытым. Все известные в настоящее время NP-полные проблемы являются NP-полными при сокращении места в журнале. Все известные в настоящее время NP-полные проблемы остаются NP-полными даже при гораздо более слабых редукциях. Однако известно, что сокращения AC определяют строго меньший класс, чем сокращения за полиномиальное время.

Именование

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

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

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

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

Свойства

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

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

См. Также

Ссылки

Цитаты

Источники

Дополнительная литература