Почему проблемы NP называются таким образом (и NP-Hard и NP-Complete)?

Question

Действительно .. У меня последний тест на выпускной в этот вторник, и это одна из вещей, которые я просто никогда не мог понять. Я понимаю, что решение проблемы NP может быть изобретена в полиноме. Но что связано с этим детерминизм?
И если бы вы могли объяснить мне, где NP-Complete и NP-трудно получили свои имена, это было бы здорово (я почти уверен, что у меня есть смысл, я просто не вижу, какие имена должны делать с тем, что они являются).
Извините, если это тривиально, я просто не могу получить его (-:
Спасибо всем!

Answer 1

п

Класс всех проблем, которые могут быть решены детерминированный Тьюринг машины в многочленом времени.

NP.

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

NP-Hard

Класс проблем, которые являются «по крайней мере, так же сложными, как самые трудные проблемы в НП». Формально проблема в NP-HARD IFF, есть проблема с NP-полной, которая является полиномиальным временем Turing-приводимым к нему; (Кроме того: IFF его можно решить в многочленом времени на машине Oracle с Oracle для проблемы). Это довольно очевидно, откуда приходит имя.

NPC.

Класс проблем, которые являются оба NP, а также NP-трудным. Относительно именования, Даже Википедия не уверен, почему он назван как оно есть.

Answer 2

Давайте начнем с «недетерминиста». Детерминированная машина может быть в одном состоянии за раз. Мы можем сделать их. Недоставленная машина - теоретическая конструкция, которая может быть в более чем на одном состоянии. (Здесь есть сходство с квантовыми вычислениями, но для наших целей здесь они вводят в заблуждение. Не обращайте внимания на них.)

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

Набор проблем, с которыми мы будем беспокоиться, является проблемами решения: учитывая заявление о проблеме, либо есть решение или нет. Найдите решение или сообщать, что нет. Например, предположим, у вас есть набор логических утверждений: a или not-b, b или c или d, не-d или a или b, .... Учитывая произвольный набор, вы можете найти значения правды для всех переменных Таким, что все утверждения верны?

Теперь давайте рассмотрим P. Предположим, что мы представляем размер проблемы с помощью n. Размер может быть количество городов в продвижении продавца, количество логических утверждений в задаче выше, что угодно. Учитывая определенный N, проблема потребует определенного количества ресурсов для решения на данной системе. Теперь, если мы удвоили ресурсы или вычислительные способности, что происходит с размером проблемы, мы можем решить? Если проблема имеет сложность полиномиальной сложности, что означает, что в P размер поднимается по определенной фракции. Это может удвоить или идти на 40% или на 10%. Напротив, если это экспоненциальная сложность, размер поднимается на определенное число. Как правило, мы думаем о проблемах P как разрешимые и экспоненциальные проблемы, так как неразрешимые, поскольку проблемы становятся большими, хотя это упрощение. С неформальной точки зрения, многочленная сложность способна понять вещи о проблеме последовательно, в то время как экспоненциальные приходится смотреть на все возможные комбинации.

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

Теперь на NP-Complete. Все проблемы в P находятся в NP. Для проблем A и B в NP, мы могли бы сказать, что если A находится в P, так что B. Это делается, найдя способ перезагружаться B как какую-то проблему. Проблема полной NP - это такая, что, если она находится в P, каждая проблема в NP находится в P. Как вы могли догадаться, найдя способ переставать все возможные проблемы, так как один конкретный был нелегко, и я буду Просто говорите, что проблема с логическими заявлениями выше (проблема удовлетворенности) была первой доказанной NP-полной. После этого было проще, поскольку было необходимо только доказать, что если проблема C была в P, поэтому была удовлетворена.

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

Есть проблемы, которые не вписываются в эту форму. Проблема продавца по путешествиям, как обычно поставлено, на сайте все города. Это не проблема в решении, и мы не можем проверить любое предложенное решение напрямую. Мы можем пересматривать его как проблему решения: Учитывая стоимость C, есть ли маршрут, который дешевле, чем C? Эта проблема является NP-Complete, а с небольшой работой мы можем решить оригинальную TSP примерно так же легко, как модифицированная, NP-полная форма. Следовательно, TSP NP-HARD, поскольку он по крайней мере, так же сложен, как проблема с NP.

Answer 3

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

Answer 4

Давайте начнем с NP: в NP, n для «недетерминированного» и P предназначен для «многочлена». Это класс проблем, которые могут быть решены в многочленом времени, если у вас есть недетерминированная машина Turging, которая может вешать в каждом цикле, чтобы исследовать возможности параллельно («Убедитесь, что решение» альтернативное определение в последнее время стало популярным, но он не проясняет что означает «n»). Недетерминиристическая машина может сравниться с параллельным компьютером с бесконечным количеством процессоров, а также способность fork() на каждой инструкции.

Сказав, что проблема q - «NP-HARD» означает, что любая проблема в NP может быть уменьшена к задаче Q (в полиноме). Поскольку отношение «может быть уменьшено до« между проблемами », является отношением порядка, вы можете подумать о« NP-Hard »как значение« по крайней мере, так же сложно, как все проблемы NP ».

Проблема «NP-полная» - это просто одна из проблем в NP, которая является NP-HARD. Я думаю, что класс проблем нуждался в имени, но я не уверен, как объяснить выбор слова «полный».

Answer 5

Но что связано с этим детерминизм?

От Википедия:

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

Не уверен в истории имени, хотя. Редактировать: У меня догадки, хотя. Далее следует спекуляция, но я не думаю, что это необоснованно.

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

Если любая единственная проблема в NP-Complete может быть решена быстро, то каждая проблема в NP также может быть решена быстро. Следовательно, полный набор проблем NP может быть решен.

Редактировать2.: Wikipedia завершится (сложность) Статья указывает:

Вычислительная проблема завершена для класса сложности, если оно в формальном смысле, один из «самых сложных» или «самых выразительных» проблем в классе сложности