Die Milleniumsprobleme sind sieben besonders haarige mathematische Probleme, deren Lösung mit einer Million Dollar belohnt wird, dies hat das Clay-Institute 2000 ausgelobt. Bislang ist eines davon, die Poincare-Vermutung, von Zotti dem Urviech Grigori Perelman gelöst worden, der die Million aus Protest gegen das Mathematik-Establishment abgelehnt hat. Äh ja.
Jetzt wirft ein Herausforderer seinen Hut in Form eines Papers in den Ring um das Problem der Komplexitätstheorie: Ist P = NP? Vinay Deolalikar ist ein bekannter Forscher, der allerdings für die HP Labs arbeitet. Und so ganz nebenher hat er wohl auch noch am P=NP-Problem gearbeitet, und jetzt einen möglichen Beweis geliefert, dass P ≠ NP ist (wie man es erwartet, aber eben noch nicht bewiesen hat).
Einfach ausgedrückt hieße das: Es gibt schwierige Probleme.
Natürlich gibt es mögliche Beweise zuhauf, die meisten davon sind das Papier nicht wert das man in den Mülleimer wirft; aber dieser Fall hier wird sehr ernst genommen. Auch wenn der Beweis sich als nicht vollständig herausstellen wird, scheint es eine bedeutende Arbeit zu sein. Scott Aaronson aber ist so skeptisch, dass der gleich 200000 $ zusätzlich auslobt, falls der Beweis richtig ist. Die Grundgeschichte erinnert ja schonmal an Andrew Wiles und Fermats Letzten Satz.
Worum geht es denn nun? P ≠ NP ist das große offene Problem der theoretischen Informatik. Es geht dabei um die Laufzeit von Algorithmen und darum, dass manche Probleme keine Lösung in polynomieller Ordnung haben. Einfache Beispiele für die Komplexität von Algorithmen kennt man aus Anfängervorlesungen in Informatik, z.B. von Sortieralgorithmen. Ein naiver Algorithmus vergleicht beispielsweise jedes Element mit jedem anderen, deswegen steigt die Zeit die man benötigt quadratisch an, man sagt die Laufzeit ist O(n²), oder “von der Ordnung n²”. Effizientere Algorithmen schaffen sowas wie O(n log n).
Es gibt aber Probleme die zwar einfach erscheinen aber nicht einfach lösbar sind. Ihre Laufzeit steigt exponentiell und schon bei vergleichsweise lächerlich wenigen Elementen sind sie nicht mehr optimal lösbar. Das klassische Beispiel ist das vom Handlungsreisenden, der eine Route sucht, um alle Orte abzuklappern an denen er Geschäfte betreiben will. Er sucht die kürzeste Route die alle Orte genau einmal besucht. Tatsächlich, das ist ein hartes Problem.
Man kann sich behelfen, und Näherungslösungen finden für die man sogar beweisen kann dass sie einen gewissen Höchstabstand vom Optimum haben. Aber wäre es nicht fein, das Problem in polynomieller Zeit lösen zu können?
Die Komplexitätsklasse P umfasst diejenigen Probleme, die sich in polynomieller Zeit lösen lassen. Das heißt die Laufzeit ist O(nc) für ein endliches positives c. Wenn c 12032902 ist hat man natürlich trotzdem verloren, aber es geht ums Prinzip.
Die Definition für NP ist leider deutlich technischer, es sind NICHT einfach die Probleme die sich nicht polynomiell lösen lassen. Das N steht für “nichtdeterministisch”. Probleme aus NP lassen sich vermutlich nicht polynomiell lösen, aber ihre Lösungen sind in polynomieller Zeit überprüfbar. Die genauere Definition braucht aber nichtdeterministische Turingmaschinen.
Turingmaschinen sind der Computer der theoretischen Informatik. Man stellt sich nur ein Band vor, das mit Feldern versehen ist die Zeichen tragen. Jedes Computerprogramm kann man jetzt theoretisch so darstellen, dass ein Lesekopf das Band abfährt und das aktuelle Zeichen liest. Je nach angetroffenem Zeichen und je nach Zustand der Maschine überschreibt der Lesekopf das Zeichen und fährt dann, wieder je Zeichen und Zustand, nach links oder rechts weiter. Die Zustände die man durchläuft und die Zeichen auf dem Band, das ist alles was man braucht um jedes Computerprogramm der Welt theoretisch auszudrücken. Jede Programmiersprache der Welt die dazu in der Lage ist eine solche einfache Maschine zu steuern ist Turing-vollständig, und dazu gehören wenige Voraussetzungen – im Vergleich dazu was Computer aus unserer Draufsicht leisten. Dies ist aber eine deterministische Turing-Maschine. Zustand und Zeichen beschreiben vollständig was passieren wird.
Es existiert eine (theoretische!) Erweiterung der Turingmaschine, die nichtdeterministische Turing-Maschine. Hier ist der nächste Schritt nicht mehr eindeutig durch Zeichen und Zustand festgelegt, stattdessen gibt es eine Menge an möglichen Übergängen. Wie diese entschieden werden, verstecken die theoretischen Informatiker leider im Symbol-Geröll…
Jedenfalls sind Probleme der Klasse NP diejenigen, die von der (theoretischen!) nichtdeterministischen Turingmaschine in polynomieller Zeit lösbar wären.
Außerdem sind die meisten NP-Probleme auch NP-vollständig. Sie fallen alle in einen Ring von Problemen, die sich alle lösen lassen wenn und wie man eines davon lösen kann. Das bedeutet (Trommelwirbel): wenn man eines davon in polynomieller Zeit lösen könnte, wären alle in polynomieller Zeit lösbar.
Und eben das ist der Heilige Gral der theoretischen Informatik. Natürlich vermutet man dass es wirklich eine Menge an Problemen gibt, die nicht polynomiell lösbar sind, aber man hat noch nicht (mathematisch) bewiesen, dass eben nicht doch P=NP ist.
Bis jetzt. Eventuell.
Kommentare (24)