P = NP ?

Ich bin gerade dabei für die erfahrungsgemäß wichtigste / schwierigste Klausur meines Bachelor-Studiums zu pauken. Sie trägt den weniger aussagekräftigen Namen "Informatik III". Grob gesagt geht es in der Vorlesung um grundlegende Algorithmen (= Verfahren, Probleme zu lösen) und die dazugehörigen Datenstrukturen. Die wichtigste Kennziffer um Algorithmen zu bewerten ist die Laufzeit. Man bedient sich dabei einigen Tricks um die Darstellung zu vereinfachen. So werden Konstanten, die von der jeweiligen Architektur des zugrunde liegenden Systems abhängen, einfach weggelassen und nur die Worst-Case Laufzeit asymptotisch angegeben. Ein kleines Beispiel zur Veranschaulichung: Ein Algorithmus erhält eine Eingabe der Länge n (z.B. eine Folge von n ganzen Zahlen). In dem Programm gibt es eine Schleife, die die Eingabe durchläuft und erst abbricht, wenn etwas bestimmtes gefunden wurde. Es könnte sein, dass die komplette Folge durchlaufen werden muss, bis die Abbruchbedingung erreicht wird (= worst-case) oder der Algorithmus schon bei der ersten Zahl anhält (= best-case). Die Laufzeit dieses Programms wäre damit O(n). Die O-Notation hier bedeutet, n-mal durchlaufen oder eben besser.

Wieso erzähle ich das ganze? Ich will auf das Thema der NP-Vollständigkeit eingehen, ein sehr interessantes Kapitel der Vorlesung, das mich fasziniert. Es geht um die Frage "P = NP?". Was ist P und was ist NP?

Um das zu erklären, muss ich erstmal weiter ausholen. Wichtig ist zu wissen, dass nur Algorithmen mit polynomieller Laufzeit für die Praxis interessant sind. Polynomiell heißt, dass nur konstante Zahlen in der Potenz der Laufzeit stehen dürfen. Also Laufzeiten wie O(n²) oder O(nÂł) sind polynomiell. Alles was langsamer läuft (exponentiell) ist äußerst ineffizient und für die Praxis unbrauchbar. Hier eine Grafik, die das sehr gut veranschaulicht. Darauf seht ihr, wie verschiedene Laufzeiten die Dauer eines Programms beeinflussen. Wie unschwer zu sehen ist, sind exponentielle Laufzeiten völlig inakzeptabel. So benötigt beispielsweise ein exponentieller Algorithmus bei Eingabelänge n = 60 (was nicht viel ist) 366 Jahrhunderte bis die Berechnung beendet ist, während ein 2-polynomieller dafür gerade einmal 36 Tausendsel Sekunden benötigt:

Nun gibt es ein Modell aus der theoretischen Informatik, das es ermöglicht, Probleme, dessen Lösung in der Praxis nur exponentiell berechnet werden können, polynomiell zu lösen. Dieses Modell trägt den netten Namen "nichtdeterministische Turing-Maschine" (NTM) und geht zurück auf Alan Turing, der dieses Modell 1936 erfunden hat. Es handelt sich bei einer NTM um eine sehr abgespeckte Version eines Computers mit einer besonderen Fähigkeit: sie kann raten. Da reale Computer das leider nicht können, ist dieses Modell für die Praxis relativ unbrauchbar. Eine deterministische Turing-Maschine (DTM) dagegen, ist ein Berechnungsmodell, das laut der Churchschen These genauso mächtig ist, wie jeder reale Computer. Man benutzt diese einfachen Rechenmodelle um Verfahren für komplexe Probleme auf eine verhältnismäßig einfache, gemeinsame Grundlage zu stellen. Wenn es um Turing-Maschinen geht, redet man nicht mehr von durchführbaren Berechnungen, sondern von akzeptierten Sprachen. Wieso das so ist, ist jetzt uninteressant. Die Menge der Sprachen, die von einer NTM in polynomieller Laufzeit akzeptiert werden, heißt NP. Und die Sprachen, die von DTMs polynomiell akzeptiert werden P. Zusammenfassend ist also P die Menge der Probleme, für die es einen effizienten, praxistauglichen Algorithmus gibt und NP die Menge der Probleme, für die es nur einen tauglichen Algorithmus gibt, wenn Computer die Lösung "erraten" könnten. Bis hierhin noch relativ unspektakulär. Nun gibt es aber unter den Sprachen in NP eine winzig-kleine Teilmenge, die Menge der NP-vollständigen Sprachen, mit einer zauberhaften Eigenschaft:

Gibt es einen polynomiellen Algorithmus für eine NP-vollständige Sprache, gilt P = NP.

Was bedeutet das? Das bedeutet, wenn man einen effizienten Algorithmus für eine NP-vollständige Sprache findet, hat man damit bewiesen, dass es für alle bisher ungelösten NP-Probleme einen effizienten Algorithmus gibt und das sind verdammt viele. Das liegt daran, dass NP-vollständige Sprachen gewissermaßen so "schwierig" sind, dass man alle anderen NP-Sprachen darauf reduzieren kann (Stichwort polynomieller Reduktionsbeweis). Um NP = P zu beweisen genügt also die effiziente Lösung einer einzigen NP-vollständigen Sprache. Wo gibts schon sowas? Um tausende Probleme zu lösen, genügt die Lösung für ein einziges zu finden. Krass oder? Und jetzt kommt der nächste Knaller: Das P-NP-Problems gehört zu den Clay Mathematics Institute Millenium-Problemen . Mit anderen Worten, wer das Problem löst, kassiert 1 Millionen Dollar. Wie schaut also so ein NP-vollständiges Problem aus, dessen Lösung einen zum Millionär macht und mit Einstein gleichstellt?

Die erste NP-vollständige Sprache wurde von Stephen A. Cook in den 70ern gefunden, das sogenannte Erfüllbarkeitsproblem der Aussagenlogik (engl. satisfiability): Jeder kennt logische Ausdrücke. Beispielsweise ist die Aussage "A und B" nur wahr, wenn A = wahr und B = wahr gilt. Es gibt also eine Belegung, für die die Aussage "A und B" wahr ist, die Aussage ist damit erfüllbar. Nun schauen die meisten formalen logischen Aussagen ein bisschen komplizierter aus (neben "und" gibt es noch zahlreiche andere logischen Verknüpfungen wie "oder", "impliziert", "ist äquivalent", etc..) und man kann sich denken, es wäre nützlich, wenn es ein Programm gäbe, das mir für beliebig lange logische Ausdrücke sagt, ob die Aussage überhaupt für irgend eine Belegung erfüllbar ist. Intuitiv könnte man einfach einen Algorithmus schreiben, der in alle Elementaraussagen (Atome) "wahr" oder "falsch" einsetzt und guckt ob irgendwann mal die Gesamtaussage wahr wird. Wie wäre die Laufzeit eines solchen Algorithmus? Bei Eingabelänge n müsste man im worst-case in alle Atome zwei Werte einsetzen (wahr oder falsch). Also eine Laufzeit von O(2^n) -> exponentiell -> inakzeptabel. Dass diese Sprache in NP liegt, sieht man leicht. Die NTM rät einfach eine Belegung und prüft ob die Gesamtaussage wahr wird. Das kann sie in polynomieller Zeit. Der Beweis, dass dieses Problem NP-vollständig ist, ist unglaublich kompliziert und eine geistige Meisterleisung von Cook. Laut unserem Prof zählt dieser Beweis (den ich absolut nicht checke) zu den größten Meilensteine der Informatik.

Bis heute wurde weder bewiesen noch wiederlegt, dass P = NP gilt. Wem es also gelingt, einen Algorithmus zu finden, der das oben beschriebene Problem in polynomieller Laufzeit löst, kassiert eine Millionen Dollar, verändert die Menschheit (Computer würden noch viel viel viel viel mächtiger werden) und kriegt neben massig Anerkennung bestimmt noch den Nobel-Preis. Also Leute, macht euch ran und findet eine polynomielle Lösung. Wenn euch das obige Problem nicht gefällt, sucht euch ein anderes NP-vollständiges Problem. Es gibt mittlerweile über 1000 davon. Für den Anfang: hier eine Liste von 21 weiteren Problemen, dessen polynomielle Lösung euch berühmt machen wird. Der Vollständigkeit halber, hier noch die offizielle Beschreibung des NP-P-Problems von Stephen Cook persönlich. Ein Ausschnitt:

The importance of the P vs NP question stems from the successful theories of NP-completeness and complexity-based cryptography, as well as the potentially stunning practical consequences of a constructive proof of P = NP.

Ich hoffe die Lösung eines solchen Problems wird keine Klausur-Aufgabe, zutrauen würde ichs unserem Prof ;)