Что такое NP и NP-полные проблемы?

Ответ 1

Существует много способов мышления о NP и NP -полноте. Я начну с определения NP, а затем расскажу о NP - жесткости и, наконец, NP -полноте.

На высоком уровне P и NP являются классами проблем. Проблема в P, если это вопрос "да" или "нет" (проблема ), и есть некоторые алгоритм, который решает проблему в полиномиальное время. Например, вопрос "можете ли вы получить от node u до node v на этом графике?" принадлежит P, потому что вы можете решить его с помощью поиска по глубине. (Обратите внимание, что сам DFS не находится в P, поскольку DFS - это алгоритм, а не проблема). Другим примером проблемы в P будет проверка, упорядочена ли последовательность в порядке сортировки.

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

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

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

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

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

(Некоторые проблемы имеют это последнее свойство - любая проблема в NP может быть эффективно преобразована в эту проблему - но сама не находится в NP. Эти проблемы называются NP -Жесткий.)

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

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

Надеюсь, это поможет!

Ответ 2

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

Ответ 3

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

Несколько вопросов

• DFS не является проблемой NP-Hard, поэтому его NP не завершен.
• NP-полнота должна быть сформулирована с точки зрения решения проблемы - я не знаю, что вы имеете в виду, приняв неправильное решение.
• Размер ввода не имеет ничего общего с NP-полнотой или твердостью. Каждая проблема имеет время выполнения в зависимости от размера проблемы, величина этой функции - это то, как определяется поли-время (а именно, если оно является полиномиальным или экспоненциальным)