P-NP-Problem: Der Angriff auf das größte Problem der Informatik ist gescheitert

Vor drei Wochen glaubte der Bonner Professor Norbert Blum, das berühmte P-NP-Problem gelöst zu haben. Nun zieht er seinen Beweis zurück.

von Manon Bischoff

Ein verzweifelter Dreitagebartträger schreit vor dem Hintergrund einer formelbedeckten Schiefertafel seinen Frust über die Unzugänglichkeit der Zahlenwelt heraus — © tiero / Getty Images / iStock (Ausschnitt)

Wochenlang waren Informatiker und Mathematiker in Aufruhr. Norbert Blum, ein renommierter Wissenschaftler der Universität Bonn, hatte am 11. August einen Beweis ins Internet gestellt, mit dem er das wohl berühmteste Rätsel der Informatik gelöst haben wollte: das so genannte P-NP-Problem.

Die Lösung hätte weit reichende Folgen für die Computerwissenschaft gehabt und Blum zum Millionär gemacht, schließlich zählt P-NP zu den sieben hoch dotierten "Millennium-Problemen". Doch nun hat Blum seinen Kommentar zurückgezogen. "Der Beweis ist falsch", schreibt der Bonner Professor auf der Internetplattform Arxiv, auf der zuvor sein Aufsatz stand.

Die Komplexität von Sudoku

Beim P-NP-Problem geht es um die Frage, ob schwierige Probleme durch effiziente Algorithmen gelöst werden können. Probleme werden mit wachsender Größe komplizierter. Ein aus neun Kästchen bestehendes Sudoku-Rätsel ist sehr schnell zu lösen, im Gegensatz zu einem, das aus 144 Kästchen besteht. Bei Problemen, die zur Klasse P ("polynomiell") gehören, wächst die Lösungszeit polynomiell – und somit effizient – mit der Länge des Problems.

Probleme, die zu NP ("nicht-deterministisch polynomiell") gehören, sind komplizierter. Sie zeichnen sich dadurch aus, dass ihre Lösung effizient überprüfbar ist. Aber bisher haben Informatiker keine effizienten Algorithmen gefunden, um eine Lösung von NP-Problemen zu finden. Man denke an das große Sudoku-Rätsel: Es lässt sich schwer lösen, da extrem viele mögliche Wege zur Lösung offenstehen, die ein Computer alle nacheinander prüfen muss. Sobald man aber eine Lösung hat, ist es für einen Rechner ein Leichtes, deren Richtigkeit zu überprüfen.

Seit mindestens 45 Jahren gehen Computerwissenschaftler der Frage nach, ob es sich bei NP-Problemen in Wahrheit um P-Probleme handelt. In diesem Fall wären auch NP-Probleme effizient lösbar, man müsste nur noch die jeweiligen Algorithmen finden. Das hätte weit reichende Folgen, da beispielsweise moderne Verschlüsselungsverfahren auf einem NP-Problem basieren.

Der Beweis knüpft an die 1980er Jahre an

Blum präsentierte in seiner Arbeit einen Beweis für die vorherrschende Meinung, dass P und NP nicht gleich sind – die Verschlüsselungsverfahren und andere NP-Probleme blieben also harte Nüsse. Für seine Argumentation nahm er sich ein Problem vor, das in NP lag, und versuchte zu zeigen, dass kein Algorithmus existiert, der dieses effizient löst. Dadurch würden P und NP eindeutig nicht übereinstimmen. Um zu beweisen, dass ein Problem nicht effizient lösbar ist, verallgemeinerte und erweiterte er Ergebnisse des theoretischen Informatikers Alexander Razborov aus den 1980er Jahren.

Clique-Problem | Das Clique-Problem beschreibt die Aufgabe, die maximale Anzahl an Knoten innerhalb eines Graphen zu finden, die direkt benachbart sind. Es gehört zur Komplexitätsklasse NP. Die Abbildung zeigt einen Algorithmus zur Lösung des Clique-Problems. In diesem Fall beträgt die Clique-Zahl vier.

Dieser hatte bewiesen, dass das so genannte Clique-Problem aus NP nicht in polynomieller Zeit gelöst werden kann, wenn für dessen Lösung nur eingeschränkte logische Operationen erlaubt sind. Rechnungen aller Art können durch Schaltkreise dargestellt werden – so rechnen auch Computer. Im Allgemeinen gibt es innerhalb dieser Schaltkreise drei logische Operationen: UND, ODER und NICHT. In elektrischen Schaltkreisen entscheiden sie darüber, ob und wie Strom durch sie hindurchfließt. Razborov führte seinen Beweis für Algorithmen, die nur Schaltkreise mit UND und ODER beinhalten – so genannte monotone Schaltkreise.

P-NP schien zum Greifen nah

Damals glaubten viele Fachleute, dass man mit Razborovs Arbeit dem allgemeinen Beweis, dass P ungleich NP ist, sehr nah war, schließlich fehlte nur noch die NICHT-Operation in den Schaltkreisen. Doch dann erkannte der Informatiker Alexander Andreev, dass das so genannte Matching-Problem, das für monotone Schaltkreise keine effiziente Lösung zulässt, durch allgemeine Schaltkreise in polynomieller Zeit gelöst wird – und somit in P liegt. Dies rückte einen Beweis, dass P ungleich NP ist, in weite Ferne.

Blum glaubte in seiner Arbeit nun einen Weg gefunden zu haben, das Ergebnis von Andreev umgehen zu können. Er argumentierte, dass für eine bestimmte Art von Problemen, die Mathematiker durch ein Näherungsverfahren konstruieren können, Aussagen über monotone Schaltkreise auch auf allgemeine Schaltkreise zutreffen. Mathematiker haben in der Vergangenheit das Clique-Problem über dieses Näherungsverfahren hergeleitet, jedoch nicht das Matching-Problem. Insofern kommt es Blums Theorem zugute. So meinte er folgern zu können: Da kein monotoner effizienter Algorithmus das Clique-Problem löst, existiert auch kein allgemeiner effizienter Algorithmus. Somit wäre P ungleich NP, ohne dass es Andreevs Arbeiten widerspricht.

Matching-Problem | Beim Matching-Problem muss die größtmögliche Anzahl an Seiten innerhalb eines Graphen gefunden werden, die nicht an denselben Knoten enden. Rechts in der Abbildung entsprechen sie den grün markierten Seiten. In jedem Fall kann jeweils ein Knoten nicht mit einem anderen gepaart werden.

Übersah Blum die Arbeit einer ungarischen Kollegin?

Offenbar hat Blum dabei jedoch eine Arbeit der ungarischen Mathematikerin Eva Tardos nicht vor Augen gehabt. Sie führte einst eine abstrakte Funktion ein, um zu zeigen, dass monotone und allgemeine Schaltkreise sehr unterschiedlich sind. Tardos definierte die nach ihr benannte Funktion über das Näherungsverfahren und zeigte, dass die Lösungsdauer bei monotonen Schaltkreisen exponentiell mit der Eingabelänge anwächst.

Blums Beweis folgend sollte die Tardos-Funktion also in NP liegen. 1988 zeigte Tardos aber, dass ihre Funktion in P liegt und somit ein effizienter Algorithmus zur Lösung existiert. Dies würde Blums Beweis widerlegen. Im Informatiker-Forum stackexchange brüstet sich ein User namens "idolvon" damit, den Fehler in Norbert Blums Beweis gefunden zu haben. Blum selbst will sich bald auf seiner Website dazu äußern. Und wer weiß: Vielleicht gelingt es ihm ja, seinen Beweis noch zu retten.