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

Ответ 1

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

Покажите, что он находится в NP

Другими словами, с учетом некоторой информации 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-hard), уменьшая еще одну NP-сложную (не обязательно NP-полную) проблему до текущей проблемы, так как NP-полные проблемы подмножество NP-жестких задач (которые также находятся в NP).

Ответ 2

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

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

Подробнее см. в конце http://www.ics.uci.edu/~eppstein/161/960312.html.

Ответ 3

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

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

Ответ 4

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

• Докажите, что ваша проблема L принадлежит NP (то есть, если вы получили решение, которое вы можете проверить в полиномиальное время)
• Выберите известную NP-полную проблему L '
• Опишите алгоритм f, который преобразует L 'в L
• Докажите, что ваш алгоритм правильный (формально: x ∈ L 'тогда и только тогда, когда f (x) ∈ L)
• Докажите, что algo f работает в полиномиальное время

Ответ 5

• Познакомьтесь с подмножеством NP Полные проблемы
• Докажите NP Hardness: уменьшите произвольный экземпляр NP полной проблемы к экземпляру вашей проблемы. Это самый большой кусок пирога и где хорошо знакомство с NP Complete problems. Сокращение будет более или менее сложным в зависимости от выбранной вами NP-задачи.
• Докажите, что ваша проблема в NP: спроектируйте алгоритм, который в полиномиальное время может проверить, является ли экземпляр решением.