Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


45. NP-vollständige Probleme



Der Satz von Cook

Bei der Reduktion wird die NP-Vollständigkeit eines Problems benutzt, um die NP-Vollständigkeit eines anderen nachzuweisen. Es gibt jedoch einen Fall, wo keine Reduktion angewandt werden kann: Wie wurde die NP-Vollständigkeit des ersten Problems bewiesen? Dies gelang S. A. Cook im Jahre 1971. Cook gab einen direkten Beweis dafür an, daß das Erfüllbarkeitsproblem NP-vollständig ist: daß, falls ein polynomiale Zeit erfordernder Algorithmus für die Erfüllbarkeit existiert, alle Probleme, die NP angehören, in polynomialer Zeit gelöst werden können.

Der Beweis ist äußerst kompliziert, doch das allgemeine Verfahren kann erklärt werden. Zuerst wird eine vollständige mathematische Definition eines Automaten entwickelt, der in der Lage ist, jedes NP angehörende Problem zu lösen. Dies ist ein einfaches Modell eines als Turingmaschine bekannten Mehrzweck-Computers, der Eingabedaten lesen, bestimmte Operationen ausführen und Ausgabedaten schreiben kann. Eine Turingmaschine kann jede Berechnung ausführen, die irgendein anderer Mehrzweck-Computer ausführen kann, mit dem gleichen Zeitaufwand (bis auf einen polynomialen Faktor genau), und besitzt den zusätzlichen Vorteil, daß sie mathematisch exakt beschrieben werden kann. Mit der zusätzlichen Fähigkeit zum Nichtdeterminismus ausgestattet, kann eine Turingmaschine jedes NP angehörende Problem lösen. Der nächste Schritt bei dem Beweis besteht darin, jedes Merkmal der Maschine zu beschreiben, einschließlich der Art und Weise, wie Anweisungen ausgeführt werden, und zwar mit Hilfe derartiger logischer Formeln, wie sie bei dem Erfüllbarkeitsproblem auftreten. Auf diese Weise wird zwischen jedem NP angehörenden Problem (welches als Programm auf der nichtdeterministischen Turingmaschine ausgedrückt werden kann) und einer Instanz des Erfüllbarkeitsproblems (der Übertragung dieses Programms in eine logische Formel) eine Entsprechung hergestellt. Nunmehr besteht die Lösung des Erfüllbarkeitsproblems im wesentlichen in einer Simulation auf der Maschine durch Abarbeitung des gegebenen Programms für die gegebenen Eingabedaten, so daß eine Lösung einer Instanz des gegebenen Problems erzeugt wird. Weitere Einzelheiten dieses Beweises würden weit über den Rahmen dieses Buches hinausgehen. Glücklicherweise ist nur ein derartiger Beweis tatsächlich notwendig; es ist viel einfacher, zum Beweis der NP-Vollständigkeit eine Reduktion anzuwenden.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]