NP Hard- und NP-Complete-Klassen

Ein Problem ist in der Klasse NPC, wenn es in NP ist und wie ist hardwie jedes Problem in NP. Ein Problem istNP-hard wenn alle Probleme in NP polynomial sind, kann die Zeit darauf reduziert werden, obwohl es möglicherweise nicht in NP selbst ist.

Wenn für eines dieser Probleme ein Polynomzeitalgorithmus existiert, wären alle Probleme in NP polynomialzeitlösbar. Diese Probleme werden genanntNP-complete. Das Phänomen der NP-Vollständigkeit ist sowohl aus theoretischen als auch aus praktischen Gründen wichtig.

Definition der NP-Vollständigkeit

Eine Sprache B ist NP-complete wenn es zwei Bedingungen erfüllt

B ist in NP
Jeder A in NP ist die Polynomzeit auf reduzierbar B.

Wenn eine Sprache die zweite Eigenschaft erfüllt, aber nicht unbedingt die erste, die Sprache B ist bekannt als NP-Hard. Informell ein SuchproblemB ist NP-Hard wenn es welche gibt NP-Complete Problem A das Turing reduziert sich auf B.

Das Problem in NP-Hard kann erst in Polynomzeit gelöst werden P = NP. Wenn sich herausstellt, dass es sich bei einem Problem um einen NPC handelt, müssen Sie keine Zeit damit verschwenden, einen effizienten Algorithmus dafür zu finden. Stattdessen können wir uns auf den Entwurfsnäherungsalgorithmus konzentrieren.

NP-vollständige Probleme

Es folgen einige NP-Complete-Probleme, für die kein Polynomzeitalgorithmus bekannt ist.

Bestimmen, ob ein Graph einen Hamilton-Zyklus hat
Bestimmen, ob eine Boolesche Formel erfüllt werden kann usw.

NP-harte Probleme

Die folgenden Probleme sind NP-Hard

Das Problem der Erfüllbarkeit der Schaltung
Abdeckung einstellen
Scheitelpunktabdeckung
Problem mit dem reisenden Verkäufer

In diesem Zusammenhang werden wir nun diskutieren, dass TSP NP-vollständig ist

TSP ist NP-vollständig

Das Problem der reisenden Verkäufer besteht aus einem Verkäufer und einer Reihe von Städten. Der Verkäufer muss jede der Städte von einer bestimmten Stadt aus besuchen und in dieselbe Stadt zurückkehren. Die Herausforderung des Problems besteht darin, dass der reisende Verkäufer die Gesamtlänge der Reise minimieren möchte

Beweis

Beweisen TSP is NP-CompleteZuerst müssen wir das beweisen TSP belongs to NP. In TSP finden wir eine Tour und überprüfen, ob die Tour jeden Scheitelpunkt einmal enthält. Dann werden die Gesamtkosten der Kanten der Tour berechnet. Schließlich prüfen wir, ob die Kosten minimal sind. Dies kann in Polynomzeit abgeschlossen werden. SoTSP belongs to NP.

Zweitens müssen wir das beweisen TSP is NP-hard. Um dies zu beweisen, besteht eine Möglichkeit darin, dies zu zeigenHamiltonian cycle ≤_p TSP (da wir wissen, dass das Hamilton-Zyklus-Problem NPcomplete ist).

Annehmen G = (V, E) eine Instanz des Hamilton-Zyklus sein.

Daher wird eine Instanz von TSP erstellt. Wir erstellen das komplette DiagrammG^' = (V, E^'), wo

$$ E ^ {'} = \ lbrace (i, j) \ Doppelpunkt i, j \ in V \: \: und \: i \ neq j $$

Somit ist die Kostenfunktion wie folgt definiert:

$$ t (i, j) = \ begin {Fälle} 0 & if \: (i, j) \: \ in E \\ 1 & andernfalls \ end {Fälle} $$

Nehmen wir nun an, dass ein Hamilton-Zyklus h existiert in G. Es ist klar, dass die Kosten für jede Kante inh ist 0 im G^' wie jede Kante gehört E. Deshalb,h hat Kosten von 0 im G^'. Also wenn graphG hat einen Hamilton-Zyklus, dann Graph G^' hat eine Tour von 0 Kosten.

Umgekehrt gehen wir davon aus G^' hat eine Tour h^' von Kosten höchstens 0. Die Kosten für Kanten inE^' sind 0 und 1per Definition. Daher muss jede Kante Kosten von haben0 als die Kosten von h^' ist 0. Wir schließen daraush^' enthält nur Kanten in E.

Das haben wir bewiesen G hat einen Hamilton-Zyklus, wenn und nur wenn G^' hat höchstens eine Kostenreise 0. TSP ist NP-vollständig.