Robert Sedgewick: Algorithmen

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


45. NP-vollständige Probleme



Deterministische und nichtdeterministische Algorithmen mit polynomialer Zeit

Der große Unterschied hinsichtlich der Leistungsfähigkeit zwischen »effizienten« Algorithmen des Typs, den wir betrachtet haben, und groben »exponentiellen« Algorithmen, die jede Möglichkeit prüfen, macht es möglich, den Grenzbereich zwischen ihnen mit Hilfe eines einfachen formalen Modells zu untersuchen. Bei diesem Modell ist die Effizienz eines Algorithmus eine Funktion der Anzahl der Bits, die verwendet werden, um die Eingabedaten unter Benutzung eines »sinnvollen« Kodierungsschemas zu verschlüsseln. (Die exakte Definition von »sinnvoll« schließt alle gebräuchlichen Kodierungsschemata von Objekten für Computer ein; ein Beispiel eines nicht sinnvollen Kodierungsschemas ist eine unäre Kodierung, bei der M Bits verwendet werden, um die Zahl M darzustellen. Stattdessen sollten wir erwarten können, daß die Anzahl der Bits, die zur Darstellung der Zahl M verwendet werden, proportional zu log M ist.) Uns interessiert nur die Identifikation von Algorithmen, für die garantiert werden kann, daß sie in einer Zeit ablaufen, die proportional zu einem Polynom in der Anzahl der Bits der Eingabedaten ist. Jedes Problem, das mit Hilfe eines solchen Algorithmus gelöst werden kann, gehört per Definition zu

P:     Menge aller Probleme, die mit Hilfe deterministischer Algorithmen in polynomialer Zeit gelöst werden können.

Unter deterministisch verstehen wir, daß zu jedem Zeitpunkt, gleichgültig, was der Algorithmus tut, nur eine Sache existiert, die er als Nächstes tun könnte. Dieser sehr allgemeine Begriff beschreibt die Art und Weise, in der Programme auf heutigen Computern ablaufen. Beachten Sie, daß das Polynom in keiner Weise vorgegeben ist und daß diese Definition mit Sicherheit die standardmäßigen Algorithmen einschließt, die wir bisher untersucht haben. Sortieren gehört zu P, da (zum Beispiel) Insertion Sort in einer zu N2 proportionalen Zeit abläuft (die Existenz von Algorithmen für das Sortieren mit zu N log N proportionaler Laufzeit ist im vorliegenden Zusammenhang unerheblich.) Die für einen Algorithmus benötigte Zeit hängt offensichtlich auch von dem verwendeten Computer ab, doch es zeigt sich, daß die Benutzung eines anderen Computers die Laufzeit nur über einen polynomialen Faktor beeinflußt (wiederum innerhalb sinnvoller Grenzen), so daß auch das für die vorliegende Betrachtung nicht besonders wesentlich ist.

Natürlich beruhen die theoretischen Ergebnisse, die wir hier vorstellen, auf einem vollständig definierten Berechnungsmodell, in dessen Rahmen die allgemeinen Aussagen, die wir machen, bewiesen werden können. Unsere Absicht ist die Betrachtung einiger prinzipieller Ideen, nicht jedoch die Entwicklung exakter Definitionen und die Herleitung von Sätzen. Der Leser kann davon ausgehen, daß alle scheinbaren logischen Unzulänglichkeiten auf den informalen Charakter der Beschreibung und nicht auf die Theorie selbst zurückzuführen sind.

Ein »unvernünftiger« Weg, die Möglichkeiten eines Computers zu erweitern, besteht darin, ihn mit der Fähigkeit des Nichtdeterminismus auszustatten: zu behaupten, daß ein Algorithmus, wenn er mit der Möglichkeit der Wahl zwischen mehreren Varianten konfrontiert wird, die Fähigkeit hat, die richtige zu »erraten«. Für die Zwecke der nachfolgenden Untersuchungen können wir uns einen Algorithmus für einen nichtdeterministischen Automaten als ein »Erraten« der Lösung eines Problems und eine nachfolgende Prüfung, ob die Lösung korrekt ist, vorstellen. Im Kapitel 20 sahen wir, wie Nichtdeterminismus als ein Werkzeug für die Entwicklung von Algorithmen von Nutzen sein kann; hier benutzen wir ihn als theoretisches Hilfsmittel für die Klassifikation von Problemen. Wir bezeichnen

NP:     Menge aller Probleme, die mit Hilfe nichtdeterministischer Algorithmen in polynomialer Zeit gelöst werden können.

Offensichtlich gehört jedes Problem, das P angehört, auch NP an. Doch es hat den Anschein, daß auch viele andere Probleme NP angehören: Um zu zeigen, daß ein Problem NP angehört, brauchen wir nur einen in polynomialer Zeit ablaufenden Algorithmus zu finden, mit dem nachgeprüft werden kann, daß eine gegebene Lösung (die erratene Lösung) richtig ist. Zum Beispiel gehört die mit »ja-nein« zu beantwortende Variante des Problems des längsten Pfades NP an. Ein anderes Beispiel eines NP angehörenden Problems ist das Erfüllbarkeitsproblem. Wenn eine logische Formel der Form

(x1 + x3 + x5) * (x1 + not x2 + x4) * (not x3 + x4 + x5) * (x2 + not x3 + x5)

gegeben ist, wobei die xi boolesche Variablen sind (wahr oder falsch), »+« die Operation ODER, »*« die Operation UND und not x die Operation NICHT bezeichnet, so besteht das Erfüllbarkeitsproblem in dem Nachweis, ob eine Zuweisung von Wahrheitswerten zu den Variablen existiert, daß die Formel »wahr« ist («erfüllt« wird). Weiter unten werden wir sehen, daß dieses spezielle Problem in der Theorie eine besondere Rolle spielt.

Nichtdeterminismus ist eine so leistungsfähige Operation, daß es beinahe absurd zu sein scheint, sie ernsthaft zu untersuchen. Warum sollte man sich die Mühe machen, ein imaginäres Werkzeug zu betrachten, das komplizierte Probleme trivial aussehen läßt? Die Antwort lautet, daß, so leistungsfähig der Nichtdeterminismus zu sein scheint, es noch niemandem gelungen ist zu beweisen, daß er für irgendein spezielles Problem von Nutzen ist! Anders ausgedrückt, es ist noch niemandem gelungen, auch nur ein einziges Problem zu finden, für das bewiesen werden kann, daß es NP angehört, aber nicht P (oder wenigstens zu beweisen, daß ein solches Problem existiert); wir wissen nicht, ob P = NP gilt oder nicht. Dies ist eine sehr unbefriedigende Situation, da viele wichtige praktische Probleme NP angehören (sie könnten mit einem nichtdeterministischen Automaten in effizienter Weise gelöst werden), jedoch nicht bekannt ist, ob sie P angehören (wir kennen bei Verwendung eines deterministischen Automaten keinen effizienten Algorithmus für sie bei Verwendung eines deterministischen Automaten). Wenn wir beweisen könnten, daß ein Problem nicht P angehört, könnten wir die Suche nach einer effizienten Lösung für dieses Problem aufgeben. Wenn ein solcher Beweis nicht erbracht wurde, besteht die Möglichkeit, daß ein effizienter Algorithmus noch nicht entdeckt wurde. Tatsächlich könnte in Anbetracht des gegenwärtigen Standes unserer Kenntnisse für jedes Problem in NP ein effizienter Algorithmus existieren, was bedeuten würde, daß noch viele effiziente Algorithmen nicht entdeckt wurden. Praktisch glaubt niemand, daß P = NP ist, und es sind beträchtliche Anstrengungen unternommen worden, um das Gegenteil zu beweisen, doch dies bleibt ein ungelöstes, offenes Problem für die Informatik.


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