Как доказать, что проблема является NP полной?

108

У меня проблема с расписанием. Мне нужно доказать, что проблема NP-полная. Какими могут быть методы, чтобы доказать это NP полной?

algorithm тетна
источник
Прочтите «Сводимость среди комбинаторных проблем» Карпа.
Пол Ханкин

Ответы:

146

Чтобы показать, что проблема завершена, вам необходимо:

Показать это в НП

Другими словами, Cимея некоторую информацию , вы можете создать алгоритм полиномиального времени, Vкоторый будет проверять для каждого возможного ввода X, Xнаходится ли он в вашем домене или нет.

пример

Докажите, что проблема покрытий вершин (то есть, для некоторого графа G, есть ли у него множество покрытий вершин такого размера k, что каждое ребро в Gимеет хотя бы одну вершину в множестве покрытий ?) Находится в NP:

  • наш ввод X- это некоторый график Gи некоторое число k(это из определения проблемы)

  • Примите нашу информацию Cкак «любое возможное подмножество вершин в графе Gразмера k»

  • Тогда мы можем написать алгоритм , Vкоторый, учитывая G, kи Cвернемся , что множество вершин , является ли вершина крышкой для Gили нет, в полиномиальное время .

Тогда для каждого графа G, если существует какое-то «возможное подмножество вершин в Gразмере k», которое является вершинным покрытием, то он Gнаходится в NP.

Обратите внимание, что нам не нужно искать Cза полиномиальное время. Если бы мы могли, проблема была бы в `P.

Обратите внимание, что алгоритм Vдолжен работать для всех G , для некоторых C. Для каждого ввода должна существовать информация, которая могла бы помочь нам проверить, относится ли ввод к проблемной области или нет. То есть не должно быть входа, где информации нет.

Докажи это NP Hard

Это включает в себя получение известной NP-полной проблемы, такой как SAT , набора логических выражений в форме:

(A, B или C) и (D, E или F) и ...

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

Затем уменьшите NP-полную проблему до вашей проблемы за полиномиальное время .

То есть, учитывая некоторый вход Xдля SAT(или любого NP-полной задачи вы используете), создать некоторый вклад Yвашей проблемы, такой , что Xнаходится в SAT тогда и только тогда , когда Yв вашей проблеме. Функция f : X -> Yдолжна выполняться за полиномиальное время .

В приведенном выше примере входными Yданными будут график Gи размер вершинного покрытия k.

Для полного доказательства вам нужно доказать оба:

  • это Xв SAT=> Yв вашей проблеме

  • а Yв твоей проблеме => Xв SAT.

В ответе marcog есть ссылка на несколько других NP-полных проблем, которые вы могли бы свести к своей проблеме.

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

Лайла Агаева
источник
7
Интересно, есть ли за этим недостающие данные или круговая аргументация. Я имею в виду, как «доказать», что проблема находится в NP, не относя ее к другой проблеме, которая «уже в NP»? Это как сказать «он сделан из железа, потому что его часть известна как железо», это не доказательство железа.
Hernán Eche
6
Насколько я помню, существует теорема Кука-Левина, которая утверждает, что SAT является NP-полной. Это доказательство немного сложнее, чем то, что я изложил выше, и я не думаю, что смогу объяснить его своими словами.
Лайла Агаева
4
Чтобы быть более точным, теорема Кука-Левина утверждает, что SAT является NP-полной: любая проблема в NP может быть сведена за полиномиальное время с помощью детерминированной машины Тьюринга к проблеме определения выполнимости булевой формулы (SAT). Итак, это недостающий элемент, о котором вы спрашивали. Если вы посмотрите теорему в Википедии, там есть доказательство, и вы можете сослаться на теорему в своем доказательстве. Тем не менее, сведение SAT к конкретной задаче - это способ, которым меня учили доказывать NP-полноту.
Лайла Агаева
Итак, мой вопрос заканчивается тем, можно ли решить SAT полиномиально, т.е. проблему P = NP. Спасибо за ваш ответ.
Hernán Eche
Не могли бы вы объяснить, почему мы не можем свести NP-сложную проблему к проблеме, которую мы хотим, на втором этапе? Должна ли это быть NP-полная проблема?
MLT
23

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

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

См. Конец http://www.ics.uci.edu/~eppstein/161/960312.html для получения дополнительной информации.

Мойнудин
источник
2
+1 кто-то объяснит понятно. вместо того, чтобы сказать кучу ссылок на ключевые слова, которые я с трудом понимаю.
ColacX
22
Первое предложение идет задом наперед: вам нужно свести известную NP-полную проблему к вашей собственной проблеме. Это показывает, что ваша проблема не менее сложна, чем известная NP-полная проблема. Часть (b) также неверна: если вы нашли сокращение, значит, вы уже знаете, что ваша проблема NP-сложная; вопрос только в том, есть ли он вообще в NP (некоторые проблемы, например, проблема остановки, нет). Если он NP-жесткий, а в NP, то он NP-полный (т.е. «NP-полный» более конкретен, чем «NP-жесткий»).
j_random_hacker
1
Я бы не сказал, что а) приводит к противоречию, поскольку мы не знаем, что P! = NP.
Chiel ten Brinke
8

Чтобы доказать, что проблема L NP-полна, нам нужно проделать следующие шаги:

  1. Докажите, что ваша проблема L принадлежит NP (то есть, учитывая решение, вы можете проверить его за полиномиальное время)
  2. Выберите известную NP-полную задачу L '
  3. Опишите алгоритм f, преобразующий L 'в L
  4. Докажите, что ваш алгоритм правильный (формально: x ∈ L 'тогда и только тогда, когда f (x) ∈ L)
  5. Докажите, что алгоритм f работает за полиномиальное время
Альберт с
источник
7

Во-первых, вы показываете, что он вообще лежит в NP.

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

Lagerbaer
источник
Нет. Вам нужно показать, что вы можете перейти от полной проблемы NP к проблеме NP, чтобы доказать полноту NP И доказать, что она вообще находится в NP. NP hard не входит в это, если вы не можете доказать это в NP.
mrmemio29,
6
  1. Ознакомьтесь с подмножеством NP Complete задач
  2. Докажите твердость NP: сведите произвольный экземпляр полной проблемы NP к экземпляру вашей проблемы. Это самый большой кусок пирога, и здесь окупается знакомство с проблемами NP Complete. Сокращение будет более или менее сложным в зависимости от выбранной вами задачи NP Complete.
  3. Докажите, что ваша проблема в NP: разработайте алгоритм, который может проверять за полиномиальное время, является ли экземпляр решением.
UmNyobe
источник