Theoretische Informatik - Prinzipielle Techniken für NP-Vollständigkeitsbeweise

Nächste Seite: Einige NP-Vollständigkeitsbeweise Aufwärts: NPC Beweise Vorherige Seite: Satz von Cook Inhalt

Unterabschnitte

Prinzipielle Techniken für NP-Vollständigkeitsbeweise

Man halte sich vor Augen:

$\begin{displaymath}L\leq_{poly}K\end{displaymath}$

Spezialisierung

Spezialisierung ist die einfachste Form des Nachweises. Hierbei ist das zu reduzierende Problem L ein Spezialfall des Problems K und kann in K ,,eingebettet'' werden³². Ein Beispiel hierfür ist $3SAT\leq_{poly}SAT$ .

Lokale Ersetzung

Die Eingabe von L wird in kleinere Einheiten von K ,,zerstückelt'' und der Algorithmus K mehrmals laufen gelassen. Beispielsweise wird bei der Reduktion³³ SAT $\leq_{poly}$ 3SAT, SAT in 3SAT Formeln umgeformt, in dem die Formel mit Hilfe der De-Morgan-Regeln verändert wird.

Transformation mit verbundenen Komponenten

Diese Art des Beweises ist die am schwierigsten zu verstehende. Die Eingabe für K wird transformiert. Aus einer Eingabe für K entsteht also eine ganz andere Eingabe für L³⁴. Eine solche Transfortmation ist z.B $L(\tau) \leq_{poly} SAT$ (Satz von Cook) oder $3SAT \leq_{poly} CP$ .

Fußnoten

... werden ³²: Diese Argumentationsweise funktioniert manchmal nicht. Mir ist es schleierhaft, warum man durch Spezialisierung polynomielle Reduzierbarkeit nachweisen kann, da zum Beispiel 2SAT auch ein Spezialfall von 3SAT ist, aber 2SAT $\in$ P und 3SAT $\in$ NP. 2SAT läßt sich reduzieren, indem man einfach ein Literal verdoppelt und schon hat man 3SAT. Man kann aber getrost ein Spezialproblem L auf ein Problem K reduzieren und damit die Unentscheidbarkeit zeigen.
... Reduktion ³³: Das sehen wir später genauer.
... L ³⁴: Natürlich gibt es auch hier gewisse Transformationsregel

Nächste Seite: Einige NP-Vollständigkeitsbeweise Aufwärts: NPC Beweise Vorherige Seite: Satz von Cook Inhalt