NP-полнота - NP-completeness - Wikipedia

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

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

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

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

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

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

Обзор

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

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

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

Смотрите также: формальное определение NP-полноты (статья P = NP)

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

1. ${\displaystyle \scriptstyle C}$ находится в NP, и
2. Каждая проблема в NP сводимый к ${\displaystyle \scriptstyle C}$ за полиномиальное время.^[2]

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

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

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

Фон

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Другой тип редукции, который также часто используется для определения NP-полноты, - это логарифмическое пространственное преобразование многих единиц что является сокращением "многие единицы", которое может быть вычислено только с логарифмическим объемом пространства. Поскольку каждое вычисление, которое может быть выполнено в логарифмическое пространство также может быть выполнено за полиномиальное время, из этого следует, что если существует редукция "многие-один" в логарифмическом пространстве, то существует также редукция "многие-один" в полиномиальном времени. Этот тип редукции является более тонким, чем более обычное полиномиальное сокращение много-единицы, и позволяет нам различать больше классов, таких как P-полный. Вопрос о том, является ли определение NP-полных изменений при этих типах редукций открытым. Все известные в настоящее время NP-полные проблемы являются NP-полными при сокращении места в журнале. Все известные в настоящее время NP-полные проблемы остаются NP-полными даже при гораздо более слабых редукциях.^[5] Однако известно, что AC⁰ редукции определяют строго меньший класс, чем редукции за полиномиальное время.^[6]

Именование

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

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

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

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

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

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

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

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

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

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

Рекомендации

Цитаты

1. Кобэм, Алан (1965). «Внутренняя вычислительная сложность функций». Proc. Логика, методология и философия науки II. Северная Голландия.
2. Дж. Ван Леувен (1998). Справочник по теоретической информатике. Эльзевир. п. 84. ISBN  978-0-262-72014-4.
3. Дж. Ван Леувен (1998). Справочник по теоретической информатике. Эльзевир. п. 80. ISBN  978-0-262-72014-4.
4. Гарей, Майкл Р.; Джонсон, Д.С. (1979). Виктор Клее (ред.). Компьютеры и непреодолимость: руководство по теории NP-полноты. Серия книг по математическим наукам. Сан-Франциско, Калифорния: W.H. Freeman and Co., стр.х + 338. ISBN  978-0-7167-1045-5. МИСТЕР  0519066.
5. Агравал, М.; Allender, E .; Рудич, Стивен (1998). "Приведение в сложности схемы: теорема об изоморфизме и теорема о разрыве". Журнал компьютерных и системных наук. 57 (2): 127–143. Дои:10.1006 / jcss.1998.1583. ISSN  1090-2724.
6. Агравал, М.; Allender, E .; Impagliazzo, R .; Питасси, Т.; Рудич, Стивен (2001). «Снижение сложности сокращений». Вычислительная сложность. 10 (2): 117–138. Дои:10.1007 / s00037-001-8191-1. ISSN  1016-3328.
7. Дон Кнут, Трейси Ларраби и Пол М. Робертс, Математическое письмо В архиве 2010-08-27 на Wayback Machine § 25, Примечания МАА № 14, MAA, 1989 (также Стэнфорд Технический отчет, 1987 г.).
8. Кнут, Д. Ф. (1974). «Терминологическое предложение». Новости SIGACT. 6 (1): 12–18. Дои:10.1145/1811129.1811130.
9. Посмотреть опрос, или [1] В архиве 2011-06-07 на Wayback Machine.
10. Болл, Филипп. «ДНК-компьютер помогает коммивояжёру». Дои:10.1038 / news000113-10.
11. Берн (1990); Deĭneko, Klinz & Woeginger (2006); Дорн и др. (2005) Ошибка harvtxt: цель отсутствует: CITEREFDornPenninksBodlaenderFomin2005 (помощь); Липтон и Тарьян (1980).
12. Hemaspaandra, L.A .; Уильямс, Р. (2012). "Колонка теории сложности новостей SIGACT 76". Новости ACM SIGACT. 43 (4): 70. Дои:10.1145/2421119.2421135.
13. Талбот, Джон; Валлийский, Д. Дж. А. (2006), Сложность и криптография: введение, Cambridge University Press, стр. 57, ISBN  9780521617710, Вопрос о том, равны ли NP и co-NP, вероятно, является второй по важности открытой проблемой в теории сложности после вопроса P и NP.

Источники

• Гарей, М.; Джонсон, Д. (1979). Компьютеры и непреодолимость: руководство по теории NP-полноты. Нью-Йорк: W.H. Фримен. ISBN  978-0-7167-1045-5. Это классическая книга, развивающая теорию, затем каталогизирующая много НП-Полные задачи.
• Кук, С.А. (1971). «Сложность процедур доказательства теорем». Труды, Третий ежегодный симпозиум ACM по теории вычислений, ACM, Нью-Йорк. С. 151–158. Дои:10.1145/800157.805047.
• Данн, П. «Аннотированный список избранных NP-полных задач». COMP202, Департамент компьютерных наук, Ливерпульский университет. Получено 2008-06-21.
• Crescenzi, P .; Канн, В .; Halldórsson, M .; Карпинский, М.; Woeginger, G. «Сборник задач оптимизации НП». KTH, Стокгольм. Получено 2020-10-24.
• Дальке, К. «NP-полные задачи». Справочный проект по математике. Получено 2008-06-21.
• Карлссон, Р. «Лекция 8: NP-полные задачи» (PDF). Кафедра компьютерных наук, Лундский университет, Швеция. Архивировано из оригинал (PDF) 19 апреля 2009 г.. Получено 2008-06-21.
• Солнце, Х. «Теория NP-полноты». Лаборатория информационной безопасности, кафедра компьютерных наук, Национальный университет Цин Хуа, Город Синьчжу, Тайвань. Архивировано из оригинал (PPT) на 2009-09-02. Получено 2008-06-21.
• Цзян, Дж. «Теория NP-полноты» (PPT). Кафедра компьютерных наук и информационной инженерии, Национальный центральный университет, Город Чжонли, Тайвань. Получено 2008-06-21.
• Кормен, Т.; Лейзерсон, К.; Ривест, Р.; Штейн, К. (2001). «Глава 34: НП - Полнота». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. С. 966–1021. ISBN  978-0-262-03293-3.
• Сипсер, М. (1997). «Разделы 7.4–7.5 (NP-полнота, Дополнительные NP-полные задачи)». Введение в теорию вычислений. PWS Publishing. стр.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 / нетто.3230200110..
• Deĭneko, Владимир Г .; Клинц, Беттина; Вёгингер, Герхард Дж. (2006). «Точные алгоритмы решения проблемы гамильтонова цикла в плоских графах». Письма об исследованиях операций. 34 (3): 269–274. Дои:10.1016 / j.orl.2005.04.013..
• Дорн, Фредерик; Пеннинкс, Элко; Бодландер, Ханс Л.; Фомин, Федор В. (2005). «Эффективные точные алгоритмы на плоских графах: использование разложений сферических ветвей». Proc. 13-й Европейский симпозиум по алгоритмам (ESA '05). Конспект лекций по информатике. 3669. Springer-Verlag. С. 95–106. Дои:10.1007/11561071_11. ISBN  978-3-540-29118-3..
• Липтон, Ричард Дж.; Тарджан, Роберт Э. (1980). «Приложения теоремы о плоском сепараторе». SIAM Журнал по вычислениям. 9 (3): 615–627. Дои:10.1137/0209046..

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

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