Wie kann man beweisen, dass ein Problem NP vollständig ist?

108

Ich habe Probleme mit der Planung. Ich muss beweisen, dass das Problem NP vollständig ist. Was können die Methoden sein, um zu beweisen, dass NP vollständig ist?

algorithm Thetna
quelle
Lesen Sie "Reduzierbarkeit bei kombinatorischen Problemen" von Karp.
Paul Hankin

Antworten:

146

Um zu zeigen, dass ein Problem NP vollständig ist, müssen Sie:

Zeigen Sie, dass es in NP ist

Mit anderen Worten, mit einigen Informationen Ckönnen Sie einen Polynomzeitalgorithmus erstellen V, der für jede mögliche Eingabe überprüft, XobX sich in Ihrer Domäne befindet oder nicht.

Beispiel

Beweisen , dass das Problem des Scheitel Abdeckungen (dass für einige Graph ist G, hat es eine Knotenüberdeckung Satz Größe hat , kso daß jede Kante in Gim Deckel Satz zumindest einen Scheitelpunkt hat ?) Ist in NP:

  • Unsere Eingabe Xist eine Grafik Gund eine Zahl k(dies stammt aus der Problemdefinition).

  • Nehmen Sie unsere Informationen Cals "jede mögliche Teilmenge von Eckpunkten in einem Diagramm Gmit Größe k".

  • Dann können wir einen Algorithmus schreiben V, der gegeben Gist kund in polynomialer ZeitC zurückgibt, ob diese Menge von Eckpunkten eine Eckpunktabdeckung ist Goder nicht .

GWenn dann für jeden Graphen eine "mögliche Teilmenge von Scheitelpunkten in Gder Größe k" existiert, die eine Scheitelpunktabdeckung ist, dann Gist in NP.

Beachten Sie, dass wir nichtC in Polynomzeit finden müssen . Wenn wir könnten, wäre das Problem in `P.

Hinweis , dass Algorithmus Vfür Arbeit sollte jeder G , für einige C. Für jede Eingabe sollte vorhanden sein Informationen , die uns helfen könnten überprüfen , ob die Eingabe im Problembereich ist oder nicht. Das heißt, es sollte keine Eingabe geben, bei der die Informationen nicht vorhanden sind.

Beweisen Sie, dass es NP Hard ist

Dies beinhaltet das Erhalten eines bekannten NP-vollständigen Problems wie SAT , der Menge von Booleschen Ausdrücken in der Form:

(A oder B oder C) und (D oder E oder F) und ...

wo der Ausdruck ist erfüllbar , dh es eine Einstellung für diesen booleans existiert, das der Ausdruck macht wahr .

Dann reduzieren das NP-vollständige Problem für Ihr Problem in Polynomialzeit .

Wenn Sie also eine Eingabe Xfür SAT(oder ein beliebiges NP-vollständiges Problem, das Sie verwenden) eingeben, erstellen Sie eine Eingabe Yfür Ihr Problem, z. XB. in SAT, wenn und nur wenn Yes in Ihrem Problem enthalten ist. Die Funktion f : X -> Ymuss in Polynomzeit ausgeführt werden .

Im obigen Beispiel Ywäre die Eingabe das Diagramm Gund die Größe der Scheitelpunktabdeckung k.

Für einen vollständigen Beweis müssten Sie beides beweisen:

  • das Xist in SAT=> Yin deinem Problem

  • und Yin deinem Problem => Xin SAT.

Die Antwort von marcog enthält einen Link zu mehreren anderen NP-vollständigen Problemen, die Sie auf Ihr Problem reduzieren könnten.

Fußnote: In Schritt 2 ( Beweisen Sie, dass es NP-hart ist ) reicht es aus, ein anderes NP-hartes (nicht unbedingt NP-vollständiges) Problem auf das aktuelle Problem zu reduzieren, da NP-vollständige Probleme eine Teilmenge von NP-harten Problemen sind (das heißt) auch in NP).

Laila Agaev
quelle
7
Ich frage mich, ob dahinter Daten oder eine Zirkelschlussfolgerung fehlen. Ich meine, wie man ein Problem in NP "beweist", ohne es auf ein anderes Problem zu verweisen, das "bereits in NP" ist? Es ist wie zu sagen "es ist aus Eisen, weil sein Teil bekanntermaßen Eisen ist", das ist kein eiserner Beweis.
Hernán Eche
6
Soweit ich mich erinnere, gibt es einen Satz namens Cook-Levin-Satz, der besagt, dass SAT NP-vollständig ist. Dieser Beweis ist etwas komplizierter als das, was ich oben skizziert habe, und ich glaube nicht, dass ich ihn in meinen eigenen Worten erklären kann.
Laila Agaev
4
Genauer gesagt besagt das Cook-Levin-Theorem, dass SAT NP-vollständig ist: Jedes Problem in NP kann in der Polynomzeit durch eine deterministische Turing-Maschine auf das Problem reduziert werden, zu bestimmen, ob eine Boolesche Formel erfüllt werden kann (SAT). Das ist also das fehlende Stück, nach dem Sie gefragt haben. Wenn Sie den Satz auf Wikipedia nachschlagen, gibt es einen Beweis, und Sie können den Satz in Ihrem Beweis referenzieren. Das heißt, die SAT auf ein bestimmtes Problem zu reduzieren, ist die Art und Weise, wie mir beigebracht wurde, die NP-Vollständigkeit zu beweisen.
Laila Agaev
Meine Frage lautet also, ob SAT im Polynom gelöst werden kann, dh das P = NP-Problem. Vielen Dank für Ihre Antwort.
Hernán Eche
Könnten Sie bitte erklären, warum wir ein NP-hartes Problem im zweiten Schritt nicht auf das gewünschte Problem reduzieren können? Muss es ein NP-vollständiges Problem sein?
MLT
23

Sie müssen ein NP-Complete-Problem auf das Problem reduzieren, das Sie haben. Wenn die Reduktion in Polynomzeit durchgeführt werden kann, haben Sie bewiesen, dass Ihr Problem NP-vollständig ist, wenn das Problem bereits in NP vorliegt, weil:

Es ist nicht einfacher als das NP-vollständige Problem, da es in Polynomzeit darauf reduziert werden kann, was das Problem NP-schwer macht.

Weitere Informationen finden Sie am Ende von http://www.ics.uci.edu/~eppstein/161/960312.html .

Moinudin
quelle
2
+1 jemand, der verständlicherweise erklärt. anstatt ein paar Verweise auf Schlüsselwörter zu sagen, verstehe ich kaum.
ColacX
22
Der erste Satz ist von hinten nach vorne: Sie müssen das bekannte NP-vollständige Problem auf Ihr eigenes Problem reduzieren. Dies zeigt, dass Ihr Problem mindestens so schwer ist wie das bekannte NP-vollständige Problem. Teil (b) ist ebenfalls falsch: Wenn Sie die Reduzierung gefunden haben, wissen Sie bereits, dass Ihr Problem NP-schwer ist; Die einzige Frage ist, ob es überhaupt in NP ist (einige Probleme, wie das Halting-Problem, sind es nicht). Wenn es NP-hart ist und in NP, dann ist es NP-vollständig (dh "NP-vollständig" ist spezifischer als "NP-hart").
j_random_hacker
1
Ich würde nicht sagen, a) führt zu einem Widerspruch, da wir nicht wissen, dass P! = NP.
Chiel zehn Brinke
8

Um zu beweisen, dass ein Problem L NP-vollständig ist, müssen wir die folgenden Schritte ausführen:

  1. Beweisen Sie, dass Ihr Problem L zu NP gehört (dh, wenn Sie eine Lösung gefunden haben, können Sie es in Polynomzeit überprüfen).
  2. Wählen Sie ein bekanntes NP-vollständiges Problem L '
  3. Beschreiben Sie einen Algorithmus f, der L 'in L umwandelt
  4. Beweisen Sie, dass Ihr Algorithmus korrekt ist (formal: x ∈ L 'genau dann, wenn f (x) ∈ L)
  5. Beweisen Sie, dass algo f in Polynomzeit läuft
Albert s
quelle
7

Zunächst zeigen Sie, dass es überhaupt in NP liegt.

Dann finden Sie ein weiteres Problem, von dem Sie bereits wissen, dass es NP vollständig ist, und zeigen, wie Sie das NP Hard-Problem polynomiell auf Ihr Problem reduzieren.

Lagerbaer
quelle
Nein. Sie müssen zeigen, dass Sie von einem NP-vollständigen Problem auf Ihr NP-Problem reduzieren können, um die NP-Vollständigkeit zu beweisen UND zu beweisen, dass es überhaupt in NP ist. NP hard kommt nicht dazu, es sei denn, Sie können nicht beweisen, dass es in NP ist.
mrmemio29
6
  1. Machen Sie sich mit einer Untergruppe von NP Complete-Problemen vertraut
  2. NP-Härte beweisen: Reduzieren Sie eine beliebige Instanz eines NP-Komplettproblems auf eine Instanz Ihres Problems. Dies ist das größte Stück eines Kuchens, bei dem sich die Vertrautheit mit NP Complete-Problemen auszahlt. Die Reduzierung wird je nach gewähltem NP Complete-Problem mehr oder weniger schwierig sein.
  3. Beweisen Sie, dass Ihr Problem in NP liegt: Entwerfen Sie einen Algorithmus, der in Polynomzeit überprüfen kann, ob eine Instanz eine Lösung ist.
UmNyobe
quelle