В чем разница между NP, NP-Complete и NP-Hard?

https://stackoverflow.com/questions/1857244

13-09-2019
|

Вопрос

Каковы различия между НП, NP-полный и NP-Жесткий?

Я знаю множество ресурсов в Интернете.Я хотел бы прочитать ваши объяснения, и причина в том, что они могут отличаться от существующих, или есть что-то, о чем я не знаю.

Решение

Я предполагаю, что вы ищете интуитивные определения, поскольку для понимания технических определений требуется немало времени.Прежде всего, давайте вспомним предварительное понятие, необходимое для понимания этих определений.

Проблема решения:Проблема с да или нет отвечать.

Теперь давайте определим эти классы сложности.

п

P — это класс сложности, который представляет собой набор всех проблем принятия решений, которые можно решить за полиномиальное время..

То есть, учитывая конкретный пример проблемы, ответ «да» или «нет» может быть принят за полиномиальное время.

Пример

Учитывая связный граф G, можно ли раскрасить его вершины в два цвета так, чтобы ни одно ребро не было однотонным?

Алгоритм:начните с произвольной вершины, раскрасьте ее в красный цвет, а всех ее соседей в синий цвет и продолжайте.Остановитесь, когда у вас закончатся вершины или вам придется сделать так, чтобы обе конечные точки ребра были одного цвета.

НП

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

Это означает, что если кто-то предоставит нам пример проблемы и сертификат (иногда называемый свидетелем) положительного ответа, мы сможем проверить его правильность за полиномиальное время.

Пример

Целочисленная факторизация находится в НП.Это проблема, в которой заданы целые числа n и m, существует ли целое число f с 1 < f < m, такой, что f делит n (f является небольшим фактором n)?

Это проблема принятия решения, потому что ответы — да или нет.Если кто-то передает нам экземпляр задачи (то есть целые числа n и m) и целое число f с 1 < f < m, и утверждать, что f является фактором n (сертификат), мы можем проверить ответ в полиномиальное время выполнив деление n / f.

NP-полный

NP-Complete — это класс сложности, который представляет собой совокупность всех задач. X в NP, для которого можно свести любую другую задачу NP Y к X за полиномиальное время.

Интуитивно это означает, что мы можем решить Y быстро, если мы знаем, как решить X быстро.Именно так, Y сводится к X, если существует алгоритм с полиномиальным временем f для преобразования экземпляров y из Y к экземплярам x = f(y) из X за полиномиальное время, с тем свойством, что ответ на y да, тогда и только тогда, когда ответ на f(y) Да.

Пример

3-SAT.Это задача, в которой нам даны союзы (И) трехпредставительных дизъюнкций (ИЛИ), утверждения вида

(x_v11 OR x_v21 OR x_v31) AND 
(x_v12 OR x_v22 OR x_v32) AND 
...                       AND 
(x_v1n OR x_v2n OR x_v3n)

где каждый x_vij — логическая переменная или отрицание переменной из конечного предопределенного списка (x_1, x_2, ... x_n).

Можно показать, что каждую задачу NP можно свести к 3-SAT.Доказательство этого является техническим и требует использования технического определения NP (на основе недетерминированных машин Тьюринга).Это известно как Теорема Кука.

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

NP-жесткий

Интуитивно, это проблемы, которые по крайней мере так же сложно, как NP-полные задачи.Обратите внимание, что NP-сложные задачи не обязательно быть в НП, и это не обязательно должны быть проблемы с решением.

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

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

Пример

А проблема с остановкой является NP-трудной задачей.Это проблема, которую дает программа P и ввод I, оно остановится?Это проблема решения, но ее нет в NP.Понятно, что любую NP-полную задачу можно свести к этой.Другой пример: любая NP-полная задача является NP-трудной.

Моя любимая NP-полная задача — Проблема сапёра.

П = НП

Это самая известная проблема в информатике и один из самых важных нерешенных вопросов в математических науках.Фактически, Институт Клэя предлагает миллион долларов за решение проблемы (Стивен Кук) записать на сайте Клея вполне неплохо).

Ясно, что P является подмножеством NP.Открытый вопрос заключается в том, имеют ли проблемы NP детерминированные решения за полиномиальное время.Многие полагают, что это не так.Вот выдающаяся недавняя статья о последней (и важности) проблемы P = NP: Статус проблемы P и NP.

Лучшая книга на эту тему Компьютеры и трудноразрешимость Гэри и Джонсон.

Другие советы

Я оглядывался вокруг и видел много длинных объяснений.Вот небольшая диаграмма, которая может быть полезна для подведения итогов:

Обратите внимание, как сложность увеличивается сверху вниз:любой NP можно свести к NP-Complete., и любой NP-Complete можно свести к NP-Hard, все за P (полиномиальное) время.

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

____________________________________________________________
| Problem Type | Verifiable in P time | Solvable in P time | Increasing Difficulty
___________________________________________________________|           |
| P            |        Yes           |        Yes         |           |
| NP           |        Yes           |     Yes or No *    |           |
| NP-Complete  |        Yes           |      Unknown       |           |
| NP-Hard      |     Yes or No **     |      Unknown ***   |           |
____________________________________________________________           V

Примечания к Yes или No записи:

* Задача NP, которая также является P, разрешима за P-время.
** Задача NP-сложная, которая также является NP-полной, поддается проверке за время P.
*** Могут быть проблемы NP-Complete (все из которых составляют подмножество NP-сложных задач).В остальном NP сложно.

я также нашел эта диаграмма весьма полезно увидеть, как все эти типы соответствуют друг другу (обратите больше внимания на левую половину диаграммы).

Это очень неформальный ответ на заданный вопрос.

Можно ли записать 3233 в виде произведения двух других чисел, больших 1?Есть ли способ обойти все Семь мостов Кенигсберга не взяв ни одного моста дважды?Это примеры вопросов, которые имеют общую черту.Возможно, неочевидно, как эффективно определить ответ, но если ответ «да», то есть короткое и быстрое доказательство для проверки.В первом случае нетривиальная факторизация 51;во втором — маршрут прогулки по мостам (с учетом ограничений).

А проблема решения представляет собой набор вопросов с ответами «да» или «нет», которые различаются только по одному параметру.Скажите, что проблема COMPOSITE={"Есть n композит": n является целым числом} или EULERPATH={"Граф G есть путь Эйлера?": G — конечный граф}.

Теперь некоторые проблемы решения поддаются эффективным, если не очевидным алгоритмам.Эйлер открыл эффективный алгоритм для решения таких задач, как «Семь мостов Кенигсберга», более 250 лет назад.

С другой стороны, для многих задач принятия решений неочевидно, как получить ответ, но если вы знаете некоторую дополнительную информацию, очевидно, как доказать, что вы дали правильный ответ.КОМПОЗИТ такой:Пробное деление — очевидный алгоритм, и он медленный:чтобы факторизовать 10-значное число, вам нужно попробовать что-то вроде 100 000 возможных делителей.Но если, например, кто-то сказал вам, что 61 — делитель 3233, простое деление столбиком — эффективный способ убедиться в правильности этих чисел.

Класс сложности НП - это класс проблем с решением, в которых ответы «да» требуют краткости формулировок и быстрой проверки доказательств.Как КОМПОЗИТ.Важным моментом является то, что это определение ничего не говорит о том, насколько сложна проблема.Если у вас есть правильный и эффективный способ решения проблемы принятия решений, достаточно просто записать шаги решения.

Исследования алгоритмов продолжаются, и постоянно создаются новые умные алгоритмы.Проблема, которую вы, возможно, не знаете, как эффективно решить сегодня, завтра может оказаться эффективным (хотя и не очевидным) решением.Фактически, исследователям потребовалось до тех пор, пока 2002 найти эффективное решение КОМПОЗИТА!Учитывая все эти достижения, действительно стоит задаться вопросом:Является ли этот отрывок о коротких доказательствах просто иллюзией?Может быть каждый Проблема принятия решения, которая поддается эффективным доказательствам, имеет эффективное решение? Никто не знает.

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

Конечно, NP — это всего лишь класс задач принятия решений.Многие проблемы не формулируются таким образом:«найти факторы N», «найти кратчайший путь в графе G, который посещает каждую вершину», «задать набор назначений переменных, которые сделают следующее логическое выражение истинным».Хотя можно неофициально говорить о том, что некоторые такие проблемы находятся «в NP», технически это не имеет особого смысла — это не проблемы решения.Некоторые из этих задач могут даже иметь ту же мощность, что и NP-полная задача:эффективное решение этих проблем (непринятия решения) приведет непосредственно к эффективному решению любой проблемы NP.Такая проблема называется NP-жесткий.

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

enter image description here

P (полиномиальное время):Как следует из названия, это проблемы, которые можно решить за полиномиальное время.

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

NP-Жесткий:Это, по крайней мере, так же сложно, как и самые сложные задачи в NP.Если мы сможем решить эти проблемы за полиномиальное время, мы сможем решить любую NP-задачу, которая только может существовать.Обратите внимание, что эти проблемы не обязательно являются проблемами NP.Это означает, что мы можем/не можем проверять решение этих задач за полиномиальное время.

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

Самый простой способ объяснить P v.NP и тому подобное, не вдаваясь в технические подробности, - это сравнивать «проблемы со словами» с «проблемами с множественным выбором».

Когда вы пытаетесь решить «словесную задачу», вам придется искать решение с нуля.Когда вы пытаетесь решить «задачу с множественным выбором», у вас есть выбор:либо решите ее, как «задачу о словах», либо попытайтесь подключить каждый из данных вам ответов и выбрать подходящий вариант ответа.

Часто бывает, что «задача с множественным выбором» гораздо проще соответствующей «задачи о словах»:подстановка вариантов ответов и проверка их соответствия может потребовать значительно меньших усилий, чем поиск правильного ответа с нуля.

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

Суть П в.НП – это вопрос:«Есть ли какие-нибудь простые задачи с несколькими вариантами ответов, которые не так просты, как задачи со словами»?То есть существуют ли задачи, для которых легко проверить достоверность данного ответа, но сложно найти этот ответ с нуля?

Теперь, когда мы интуитивно понимаем, что такое NP, нам нужно бросить вызов своей интуиции.Оказывается, существуют «задачи с множественным выбором», которые в некотором смысле являются самыми трудными из всех:если бы кто-то нашел решение одной из этих «самых сложных из всех» проблем, он был бы в состоянии найти решение ВСЕХ проблем NP!Когда Кук обнаружил это 40 лет назад, это стало полной неожиданностью.Эти «самые сложные из всех» задач известны как NP-сложные.Если вы найдете «решение словесной задачи» для одного из них, вы автоматически найдете «решение словесной задачи» для каждой «простой задачи с множественным выбором»!

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

Я думаю, мы можем ответить на этот вопрос гораздо более лаконично.Я ответил на связанный вопрос, и скопирую оттуда мой ответ

Но во-первых, NP-трудная задача — это задача, для которой мы не можем доказать существование решения за полиномиальное время.NP-трудность некоторой «проблемы-P» обычно доказывается путем преобразования уже доказанной NP-трудной задачи в «задачу-P» за полиномиальное время.

Чтобы ответить на оставшуюся часть вопроса, вам сначала нужно понять, какие NP-сложные задачи также являются NP-полными.Если NP-трудная задача принадлежит множеству NP, то она NP-полна.Чтобы принадлежать множеству NP, задача должна быть

(i) проблема решения,
(ii) число решений задачи должно быть конечным, и каждое решение должно иметь полиномиальную длину, и
(iii) учитывая решение полиномиальной длины, мы должны быть в состоянии сказать, будет ли ответ на проблему да/нет

Теперь легко увидеть, что может существовать множество NP-сложных задач, которые не принадлежат множеству NP и которые труднее решить.В качестве интуитивно понятного примера: оптимизационная версия коммивояжера, в которой нам нужно найти фактическое расписание, сложнее, чем версия для принятия решения коммивояжера, где нам просто нужно определить, существует ли расписание длиной <= k или нет.

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

Проблемы, относящиеся к классу сложности NP, могут быть решены недетерминировано за полиномиальное время, а возможное решение (т. Е. Сертификат) для проблемы в NP может быть проверено на корректность за полиномиальное время.

Примером недетерминированного решения проблемы k-клики может быть что-то вроде:

1) случайным образом выбрать k узлов из графа

2) проверить, что эти k узлов образуют клику.

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

Обратите внимание, что все задачи, детерминированно решаемые за полиномиальное время, также относятся к NP.

Чтобы показать, что проблема является NP-сложной, обычно требуется свести некоторую другую NP-сложную задачу к вашей проблеме с использованием полиномиального отображения времени: http://en.wikipedia.org/wiki/Reduction_(сложность)

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

Для тех, кто думает, что вычислительная сложность связана только с P и NP, вот самый исчерпывающий ресурс о задачах различной вычислительной сложности.Помимо задач, заданных ОП, в нем перечислено около 500 различных классов вычислительных задач с красивыми описаниями, а также список фундаментальных исследовательских работ, описывающих этот класс.

Насколько я понимаю, ан np-жесткий проблема не «сложнее», чем np-полный проблема.Фактически, по определению, каждая np-полная задача:

в НП
np-жесткий

-- Вступление.к алгоритмам (3-е издание) Кормена, Лейзерсона, Ривеста и Штейна, стр. 1069.

Найдите какое-нибудь интересное определение:

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow