Robert Sedgewick: Algorithmen

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


45. NP-vollständige Probleme



NP-Vollständigkeit

Weiter unten betrachten wir eine Reihe von Problemen, von denen bekannt ist, daß sie NP angehören, aber nicht, ob sie P angehören. Das heißt, sie lassen sich leicht mit Hilfe eines nichtdeterministischen Automaten lösen, doch trotz beträchtlicher Anstrengungen gelang es noch niemandem, für eines von ihnen einen effizienten Algorithmus auf einem herkömmlichen Automaten zu finden (oder zu beweisen, daß keiner existiert). Diese Probleme besitzen eine zusätzliche Eigenschaft, die ein überzeugendes Argument dafür liefert, daß P <> NP gilt: Falls irgendeines der Probleme in einer polynomialen Zeit auf einem deterministischen Automaten gelöst werden kann, so ist das für alle Probleme in NP möglich (das heißt, es ist P = NP). Das heißt, das kollektive Unvermögen aller Wissenschaftler, effiziente Algorithmen für alle diese Probleme zu finden, könnte als kollektives Unvermögen angesehen werden, zu beweisen, daß P = NP gilt. Solche Probleme werden NP-vollständig genannt. Es zeigt sich, daß eine große Zahl interessanter praktischer Probleme dieses Merkmal besitzt.

Das wichtigste Hilfsmittel, das angewandt wird, um zu beweisen, daß Probleme NP-vollständig sind, beruht auf der Idee der polynomialen Reduzierbarkeit. Mit Hilfe des folgenden Prozesses zeigen wir, daß ein Algorithmus zur Lösung eines neuen Problems in NP benutzt werden kann, um ein gewisses bekanntes NP-vollständiges Problem zu lösen: Transformiere irgendeine Instanz des bekannten NP-vollständigen Problems in eine Instanz des neuen Problems, löse das Problem unter Benutzung des gegebenen Algorithmus, transformiere dann die Lösung zurück in eine Lösung des NP-vollständigen Problems. Im Kapitel 34 betrachteten wir ein Beispiel eines ähnlichen Prozesses, als wir bipartite Paarung auf das Problem des Flusses in einem Netzwerk zurückführten. Unter »polynomial reduzierbar« verstehen wir, daß die Transformationen in polynomialer Zeit ausgeführt werden können; demzufolge würde die Existenz eines in polynomialer Zeit ablaufenden Algorithmus für das neue Problem die Existenz eines in polynomialer Zeit ablaufenden Algorithmus für das NP-vollständige Problem zur Folge haben, und dies würde (aufgrund der Definition) die Existenz von in polynomialer Zeit ablaufenden Algorithmen für alle Probleme in NP nach sich ziehen.

Die Idee der Reduktion (Zurückführung) liefert einen nützlichen Mechanismus für die Klassifikation von Algorithmen. Um zum Beispiel zu beweisen, daß ein NP angehörendes Problem NP-vollständig ist, brauchen wir nur zu zeigen, daß irgendein bekanntes NP-vollständiges Problem auf dieses Problem polynomial reduzierbar ist, das heißt, daß ein in polynomialer Zeit ablaufender Algorithmus für das neue Problem benutzt werden kann, um das NP-vollständige Problem zu lösen, und dann wiederum benutzt werden kann, um alle Probleme in NP zu lösen. Als Beispiel für eine Reduktion erinnern wir an die folgenden beiden Probleme aus Kapitel 44:

Nehmen wir an, wir wissen, daß das Problem des Hamilton-Zyklus NP-vollständig ist, und wir möchten feststellen, ob das Problem des Handlungsreisenden ebenfalls NP-vollständig ist oder nicht. Ein beliebiger Algorithmus für die Lösung des Problems des Handlungsreisendens kann verwendet werden, um das Problem des Hamilton-Zyklus zu lösen, indem die folgende Reduktion vorgenommen wird: Zu einer gegebenen Instanz des Problems des Hamilton-Zyklus (Graph) konstruiere man eine Instanz des Problems des Handlungsreisenden (Menge von Städten, mit Entfernungen zwischen allen Paaren) wie folgt: Als Städte für das Problem des Handlungsreisenden verwende man die Menge der Knoten im Graph; als Entfernungen zwischen jedem Städtepaar verwende man eins, wenn zwischen den entsprechenden Knoten im Graph eine Kante vorhanden ist, und zwei, wenn keine Kante vorhanden ist. Dann bestimme man mit Hilfe des Algorithmus für das Problem des Handlungsreisenden eine Tour mit einer Länge, die kleiner oder gleich N ist, der Anzahl der Knoten im Graph. Diese Tour muß exakt einem Hamilton-Zyklus entsprechen. Ein effizienter Algorithmus für das Problem des Handlungsreisenden wäre auch ein effizienter Algorithmus für das Problem des Hamilton-Zyklus. Das heißt, das Problem des Hamilton-Zyklus läßt sich auf das Problem des Handlungsreisenden zurückführen, so daß die NP-Vollständigkeit des Problems des Hamilton-Zyklus die NP-Vollständigkeit des Problems des Handlungsreisenden impliziert.

Die Reduktion des Problems des Hamilton-Zyklus auf das Problem des Handlungsreisenden ist relativ einfach, weil die Probleme so ähnlich sind. In Wirklichkeit können Reduktionen mit polynomialer Zeit sehr kompliziert sein und Probleme miteinander verknüpfen, die scheinbar sehr verschieden sind. Es ist zum Beispiel möglich, das Erfüllbarkeitsproblem auf das des Hamilton-Zyklus zurückzuführen. Ohne auf Einzelheiten einzugehen, betrachten wir die Grundidee des Beweises.

Wir möchten zeigen, daß wir, wenn eine polynomiale Zeit erfordernde Lösung des Problems des Hamilton-Zyklus vorliegen würde, mittels polynomialer Reduktion eine polynomiale Zeit erfordernde Lösung des Erfüllbarkeitsproblems erhalten können. Der Beweis besteht in einer detaillierten Konstruktionsmethode, die zeigt, wie man für eine gegebene Instanz des Erfüllbarkeitsproblems (eine boolesche Formel) eine Instanz des Problems des Hamilton-Zyklus (einen Graph) erzeugen kann (in polynomialer Zeit). Diese Instanz hat die Eigenschaft, daß man, wenn man weiß, ob der Graph einen Hamilton-Zyklus besitzt, auch weiß, ob die Formel erfüllbar ist. Der Graph wird aus kleinen Komponenten (die den Variablen entsprechen) aufgebaut, die über einen einfachen Pfad in nur einer der beiden Richtungen durchlaufen werden können (was dem Wahrheitsgehalt »wahr« oder »falsch« der Variablen entspricht). Diese kleinen Komponenten werden so miteinander verknüpft, wie es durch die logischen Operationen vorgegeben ist, wobei kompliziertere Teilgraphen verwendet werden, die entsprechend dem Wahrheitsgehalt der Verknüpfungen mittels einfacher Pfade durchlaufen werden können. Von dieser kurzen Beschreibung bis zur vollständigen Konstruktion ist es noch ein recht weiter Schritt, und die Angabe strenger, ausführlicher Beweise dieser Art ist eine schwierige Aufgabe (obwohl Spezialisten auf diesem Gebiet eine beachtliche Gewandtheit bei der Konstruktion solcher Reduktionen erwerben). Unsere Absicht hier besteht darin, die Tatsache zu illustrieren, daß polynomiale Reduktion auf recht unterschiedliche Probleme angewandt werden kann.

Wenn uns also ein polynomiale Zeit erfordernder Algorithmus für das Problem des Handlungsreisenden vorliegen würde, so würden wir auch über einen polynomiale Zeit erfordernden Algorithmus für das Problem des Hamilton-Zyklus verfügen, welcher uns auch einen polynomiale Zeit erfordernden Algorithmus für das Erfüllbarkeitsproblem liefern würde. Jedes Problem, für das bewiesen wurde, daß es NP-vollständig ist, liefert eine weitere potentielle Grundlage für den Beweis dafür, daß noch ein weiteres künftiges Problem NP-vollständig ist. Der Beweis könnte so einfach sein wie die oben angegebene Reduktion des Problems des Hamilton-Zyklus auf das Problem des Handlungsreisenden, oder so kompliziert wie die oben kurz umrissene Transformation des Erfüllbarkeitsproblems in das Problem des Hamilton-Zyklus, oder sein Schwierigkeitsgrad könnte dazwischen liegen. Für buchstäblich Tausende von Problemen aus den vielfältigsten Anwendungsgebieten ist bewiesen worden, daß sie NP-vollständig sind, indem sie auf diese Weise ineinander umgewandelt wurden.


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