12 Begriff der NP-Vollständigkeit

Definition:

(Ja-Nein-) Problem A ist in Polynomzeit reduzierbar auf Problem B (kurz: A $\ge_{P}^{}$ B )

( P = Menge aller in Polynomzeit berechenbaren Funktionen)

NP : = {L : Zu gegebener Instanz x und Beweisvorschlag y kann in Polynomzeit überprüft werden, ob y beweist: x $\in$ L} ( L = Ja-Nein-Problem)

L₀ ist NP -vollständig, wenn

1.: L₀ $\in$ NP
2.: $\forall$ L $\in$ + NP gilt: L $\ge_{P}^{}$ L₀

Nachweis der NP -Vollständigkeit, über ein ``erstes'' NP -vollständigiges Problem L₁ , für ein ``neues'' NP -vollständiges Problem L₂ durch Finden einer Reduktion L₁ $\ge_{P}^{}$ L₂ . (``Erstes'' NP -vollständigiges Problem L₁ fand Cook 1972: Satisfiability Problem) Beispiele für Reduktion:

Beispiele für Reduktion:

1.) Independent Set $\ge_{P}^{}$ Vertexcover

(siehe Abschnitt Independent Set)

2.) 3-Färbbarkeit $\ge_{P}^{}$ Independent Set

Als Ja-Nein-Problem Gibt es eine $\ge_{P}^{}$ Gibt es ein Independent Set mit

formulieren: 3-Färbung? bestimmter Anzahl von Knoten?

Behauptung:

G = (V,E) ist 3-färbbar $\iff$ G' hat Independent Set der Größe |V| .

Beweis:

$\Leftarrow$ : Aus jeder ``Dreier''-Gruppe gehört genau ein Knoten zum Independent Set I . Falls i -ter Knoten $\in$ I , färbe entsprechenden Knoten in G mit Farbe i (i = 1,2,3) .

$\Rightarrow$ : Füge jeweils i -ten Knoten aus jeder ``Dreier''-Gruppe zu I hinzu, wobei i die Farbe des entsprechenden Knotens in G ist.

Vermutung:

Es gibt keinen Polynomzeitalgorithmus mit konstanter Fehlerschranke f für das TSP .

Annahme:

Doch, es existiert ein solcher Algorithmus. Sei G = (V,E) mit n Knoten, ungerichtet. Bilde G' = (V,E') mit c : E' $\to$ $\mathbb {N}$ , (E' = V × V)

Sei A der Näherungsalgorithmus mit Schranke f . Wende A auf G' an.

1.: G hat einen Hamiltonkreis $\Rightarrow$ Opt(G') = n $\Rightarrow$ Apr(G') $\ge$ f · n
2.: G hat keinen Hamiltonkreis $\Rightarrow$ Opt(G') > f · n $\Rightarrow$ Apr(G') > f · n $\Rightarrow$ Ergebnis würde über die Existenz eines Hamiltonkreises in G befinden.

Wäre die Annahme richtig, so wäre das Hamiltonkreisproblem in Polynomzeit lösbar. (*) (Transformation G $\rightarrow$ G' erfolgt in Polynomzeit) Das Hamiltonkreisproblem ist NP -vollständig. (*) $\Rightarrow$ P = NP (sehr unwahrscheinlich)

1.)	Independent Set	$\ge_{P}^{}$	Vertexcover
			(siehe Abschnitt Independent Set)
2.)	3-Färbbarkeit	$\ge_{P}^{}$	Independent Set

Als Ja-Nein-Problem	Gibt es eine	$\ge_{P}^{}$	Gibt es ein Independent Set mit
formulieren:	3-Färbung?		bestimmter Anzahl von Knoten?

$\Leftarrow$ :	Aus jeder ``Dreier''-Gruppe gehört genau ein Knoten zum Independent Set I . Falls i -ter Knoten $\in$ I , färbe entsprechenden Knoten in G mit Farbe i (i = 1,2,3) .
$\Rightarrow$ :	Füge jeweils i -ten Knoten aus jeder ``Dreier''-Gruppe zu I hinzu, wobei i die Farbe des entsprechenden Knotens in G ist.