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

Question

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

Answer 1

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

Показать в 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) и ...

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

Тогда уменьшите проблему NP-complete до вашей задачи за полиномиальное время .

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

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

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

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

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

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

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

Answer 2

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

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

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

Answer 3

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

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

Answer 4

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

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

Answer 5

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