Robert Sedgewick: Algorithmen

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


45. NP-vollständige Probleme



Einige NP-vollständige Probleme

Wie bereits erwähnt wurde, ist für buchstäblich Tausende verschiedener Probleme bekannt, daß sie NP-vollständig sind. In diesem Abschnitt zählen wir einige davon auf, um das breite Spektrum der Probleme zu veranschaulichen, die untersucht worden sind. Natürlich beginnt die Liste mit dem Erfüllbarkeitsproblem; sie enthält das Problem des Handlungsreisenden und das des Hamilton-Zyklus sowie das des längsten Pfades. Die folgenden weiteren Probleme stehen stellvertretend für viele andere:

Diese und viele ähnlich geartete Probleme haben wichtige, praktische Anwendungen, und eine Zeitlang war ein starker Anreiz gegeben, gute Algorithmen für ihre Lösung zu finden. Die Tatsache, daß für keines dieser Probleme ein guter Algorithmus gefunden wurde, spricht sicher sehr stark dafür, daß P <> NP gilt, und die meisten Fachleute sind davon überzeugt, daß das der Fall ist. (Andererseits könnte die Tatsache, daß es niemandem gelang zu beweisen, daß irgendeines dieser Probleme nicht P angehört, als Indizienbeweis für das Gegenteil ausgelegt werden.) Ob nun P = NP gilt oder nicht, Tatsache ist, daß uns gegenwärtig keine Algorithmen zur Verfügung stehen, die garantiert irgendeines der NP-vollständigen Probleme in effizienter Weise lösen.

Wie im vorangegangenen Kapitel erwähnt, wurden diverse Methoden entwickelt, um diese Situation zu bewältigen, da in der Praxis irgendeine Lösung für diese verschiedenartigen Probleme gefunden werden muß. Ein Ansatz besteht darin, die Problemstellung zu ändern und einen »Approximationsalgorithmus« zu finden, der nicht die beste Lösung ermittelt, sondern eine Lösung, für die garantiert werden kann, daß sie der besten nahekommt. (Leider ist dies manchmal nicht ausreichend, um die NP-Vollständigkeit zu umgehen.) Eine andere Möglichkeit ist, sich auf eine »durchschnittliche« Leistungsfähigkeit zu verlassen und einen Algorithmus zu entwickeln, der in manchen Fällen die Lösung findet, aber nicht unbedingt in allen Fällen zum Ziel führt. Das heißt, auch wenn es unmöglich sein mag, einen Algorithmus zu finden, der für alle Instanzen eines Problems garantiert gut arbeitet, kann es durchaus möglich sein, praktisch alle Instanzen, die in der Praxis auftreten, in effizienter Weise zu lösen. Ein dritter Ansatz besteht darin, mit »effizienten« exponentiellen Algorithmen zu arbeiten und dabei die im vorangegangenen Kapitel beschriebenen Backtrackingmethoden zu verwenden. Letztendlich existiert eine sehr große Lücke zwischen polynomialer und exponentieller Zeit, über die die Theorie nichts aussagt. Wie steht es mit einem Algorithmus, der in einer zu Nlog N oder 2sqrtN proportionalen Zeit abläuft?

Die NP-Vollständigkeit berührt alle Anwendungsgebiete, die wir in diesem Buch betrachtet haben: NP-vollständige Probleme treten bei numerischen Anwendungen, beim Sortieren und Suchen, bei der Verarbeitung von Zeichenfolgen, in der Geometrie und bei der Verarbeitung von Graphen auf. Der wichtigste praktische Aspekt der Theorie der NP-Vollständigkeit besteht darin, daß sie einen Mechanismus liefert, mit dem festgestellt werden kann, ob ein neues Problem aus irgendeinem dieser Gebiete »leicht« oder »schwer« ist. Wenn ein effizienter Algorithmus für die Lösung eines neuen Problems gefunden werden kann, gibt es keine Schwierigkeiten. Wenn nicht, liefert ein Beweis der NP-Vollständigkeit dieses Problems zumindest die Aussage, daß die Entwicklung eines effizienten Algorithmus ein höchst erstaunliches Ergebnis wäre (und daß es empfehlenswert ist, vielleicht einen anderen Ansatz auszuprobieren). Die vielen effizienten Algorithmen, die wir in diesem Buch untersucht haben, sind ein Beweis dafür, daß wir seit Euklid eine Menge über effiziente Berechnungsmethoden hinzugelernt haben, doch die Theorie der NP-Vollständigkeit zeigt, daß wir in Wirklichkeit noch sehr viel zu lernen haben.


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