Für einen Algorithmus lässt sich gemeinhin eine grobe Hausnummer angeben, wie schnell er zu einem Ergebnis kommt. Beispiel: Unter n Zeichen nach einem bestimmten zu suchen, kostet den Computer in etwa n Schritte – er muss jedes Zeichen einmal anschauen. Für andere Probleme ist der Aufwand hingegen deutlich höher, ein Computer kommt dann beispielsweise erst nach n² oder n³ Schritten ans Ziel. Solche Probleme liegen in der Komplexitätsklasse P und gelten trotz der höheren Anforderungen immer noch als "mit vertretbarem Aufwand" lösbar.

Dagegen gibt es für Probleme, die in der Klasse NP liegen, eine solche Abschätzung nicht. Der Aufwand zu ihrer Lösung kann schnell die Grenze alles Machbaren überschreiten. Liegt der Aufwand beispielsweise in der Größenordnung 2ⁿ Rechenschritte (für n Eingaben), übersteigt die Berechnungsdauer leicht das gegenwärtige Alter des Universums. Besonders tückisch sind unter ihnen die so genannten NP-vollständigen Probleme, die unter anderem dadurch gekennzeichnet sind, dass es vermutlich keine Abkürzung gibt: Es scheint, jeder noch so raffinierte Ansatz beansprucht am Ende doch wieder maßlos viel Zeit für die Lösung.

Oder hat man die richtige Abkürzung nur noch nicht entdeckt? Für den Beweis, dass diese tatsächlich nicht existiert – oder den Beweis des Gegenteils, was auf eine Weltsensation hinauslaufen würde –, ist ein Preisgeld von einer Million US-Dollar ausgeschrieben. Die als P = NP bekannte Fragestellung zählt zu den Millennium-Problemen und hat sich bisher einer Beantwortung erfolgreich widersetzt. Das hat ganz praktische Auswirkungen, denn viele im Alltag verwendete Computerprogramme leiden darunter, dass es für manche Probleme keine Abkürzung gibt, oder machen sich im Gegenteil diesen Umstand zu Nutze, so etwa bei Verschlüsselungsverfahren.

Hartnäckiges Problem scheint schneller lösbar als gedacht

Nun jedoch könnte endlich frischer Wind in die Suche nach einer Lösung für das P-NP-Problem gekommen sein. Zumindest geht dies aus Gerüchten hervor, von denen unter anderem "New Scientist" und "Science" berichten. Hoffnung kommt aus unerwarteter Richtung: Ein Problem, das man bisher zu den schweren gezählt hat, scheint tatsächlich wesentlich näher an der "einfachen" Klasse P zu liegen als gemeinhin angenommen.

Wie der Mathematiker László Babai von der University of Chicago in Illinois in einer Vortragsreihe erläutert, kann das so genannte Graphen-Isomorphieproblem in geringfügig mehr als polynomialer Zeit gelöst werden. Mit weiteren Verbesserungen lässt es sich künftig vielleicht sogar komplett in die P-Klasse einfügen.

Wohlgemerkt: Eine Antwort auf das eigentliche P-NP-Problem verbirgt sich hinter Babais Entdeckung noch nicht. Doch dass ein Problem, das als extrem schwierig galt, eine Abkürzung bereithält, die in jahrzehntelanger Suche übersehen wurde, weckt die Hoffnung, eine solche auch für die NP-vollständigen zu finden. Darum könnte sich Babais Entdeckung als Informatiksensation des Jahrzehnts entpuppen, wie Scott Aaronson vom Massachusetts Institute of Technology findet, der in seinem Blog über die Neuigkeiten berichtet.

Wenige Details über die Lösung sind bekannt

Konkret geht es bei dem Problem der Graphenisomorphie darum zu entscheiden, ob zwei Graphen, also Netzwerke aus miteinander über Kanten verbundenen Knoten, identisch sind oder nicht. Durch reines Ausprobieren kommt man hier nicht ans Ziel: Die Zahl der Kombinationsmöglichkeiten wächst mit der Anzahl der Knoten schnell in Größen jenseits der Handhabbarkeit.

Wie Babai das Problem gelöst hat – und ob sein Ansatz überhaupt korrekt ist –, steht noch dahin. Der Wissenschaftler gibt derzeit öffentlich keine Auskünfte; den Rummel in der Blogosphäre sehe er kritisch, teilt er dem "New Scientist" mit. Zunächst sollten Fachkollegen in aller Ruhe seine Ergebnisse überprüfen. Dem Vernehmen nach zerlegt er Graphen in kleinere Einheiten und betrachtet diese einzeln. Offenbar greift er dazu auf bestimmte gruppentheoretische Konzepte zurück (die Klassifikation endlicher einfacher Gruppen). Der im Verlauf der letzten Jahrzehnte vorgelegte Beweis für diese Annahmen gelangte dank seines stattlichen Umfangs von rund 15 000 Seiten ebenfalls zu einer gewissen Berühmtheit.

Unmittelbare technische Auswirkungen werden von dem neuen Lösungsweg, sofern er Bestand hat, allerdings nicht erwartet. Um die Isomorphie zweier Graphen zu bestimmen, könne man bereits heutzutage auf Verfahren zurückgreifen, die unter üblichen Alltagsbedingungen in akzeptabler Zeit Antworten liefern, erläutert Aaronson. Die erhoffte Sprengkraft dürfte Babais Entdeckung demnach eher in der reinen Mathematik entfalten – zumindest in einem ersten Schritt.