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

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

5 88
algorithm

5 ответов:

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

показать это в NP

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

пример

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

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

  • принять нашу информацию C быть " любым возможным подмножеством вершин в графе G в размере k"

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

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

Примечание что мы делаем не нужно найти C за полиномиальное время. Если бы проблема была бы в П.

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

доказать, что это NP трудно

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

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

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

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

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

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

на полное доказательство, вы должны были бы доказать оба:

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

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

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

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

121

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

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

смотрите конец http://www.ics.uci.edu / ~eppstein/161/960312.html для большего.

21

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

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

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

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

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