http://www.faz.net/-gwz-9141l

Mathematik : Die Macht des Nein

Vieles in der Mathematik ist harmlos – einiges aber tatsächlich sensationell. Bild: dpa

Ein Bonner Mathematiker will bewiesen haben, dass „P ≠ NP“. Klingt harmlos, wäre aber sensationell. Ob der Beweis stimmt, ist allerdings noch nicht sicher.

          Zwanzig Cent hat Alexander Razborov gewettet. Der Mathematiker von der University of Chicago verliert sie an einen Kollegen, wenn sich herausstellt, dass ein vor zwei Wochen publizierter Beweis des Bonner Informatikprofessors Norbert Blum korrekt ist. Blum hingegen wäre um eine Million Dollar reicher. Denn sein Beweis betrifft das sogenannte P=NP-Problem, eines von sechs mathematischen Rätseln, auf deren Lösung die amerikanische Clay-Stiftung im Jahr 2000 die Million ausgesetzt hatte. Ein siebtes war bereits 2002 gelöst worden

          Ulf von Rauchhaupt

          verantwortlich für das Ressort „Wissenschaft“ der Frankfurter Allgemeinen Sonntagszeitung.

          Die medienwirksam hohe Dotierung markiert die besondere wissenschaftliche Wichtigkeit dieser sogenannten Millennium-Probleme, aber auch ihre mutmaßliche Schwierigkeit, gemessen auch an Mathematiker-Lebenszeit, die bisher schon auf Lösungssuche verschwendet wurde. Doch P=NP nimmt unter den Millennium-Problemen eine Sonderstellung ein.

          NP bedeutet: Schwer zu lösen, leicht zu prüfen

          Es ist beileibe nicht nur wissenschaftlich wichtig, betrifft es doch die Kerntechnologie der heutigen Zivilisation, den Computer. P und NP sind beides Mengen möglicher Aufgaben, die von digitalen Rechnern mittels Algorithmen bearbeitet werden können. Zum Beispiel die Aufgabe, eine Liste von n Zahlen der Größe nach zu sortieren. Die Frage ist nun, wie schnell die Rechenzeit mit dem Umfang des Inputs steigt. Beim Sortieren braucht ein Computer im ungünstigsten Fall für eine doppelt so lange Liste viermal so lang – die Rechenzeit wächst quadratisch oder mit n². Dieses n² ist ein einfaches Beispiel für etwas, was Mathematiker ein Polynom nennen. Sortieren gehört daher zur sogenannten Komplexitätsklasse P wie Polynom. Dazu würde auch eine Aufgabe zählen, für das die benötigte Rechenzeit, sagen wir, mit n³ anwächst, oder n¹⁰ oder n³+ n². Das alles sind Polynome, und mit P-Problemen werden moderne Rechner auch bei hohen n im Allgemeinen ganz gut fertig.

          Für viele Aufgabenstellungen sind aber keine Algorithmen bekannt, die ihre Zugehörigkeit zu P erweisen, sondern nur welche, deren Rechenzeit zum Beispiel wie 2ⁿ mit dem Input steigt, also exponentiell. Für immer größere Inputlängen n werden Computer hier so schnell langsamer, dass auch mit praktisch relevanten n selbst die leistungsfähigsten Großrechner Milliarden von Jahren beschäftigt wären. Zu den Problemen, für die es nur solche Algorithmen gibt, zählt die Zerlegung n-stelliger Zahlen in Faktoren. Dies machen sich zum Beispiel die gängigen Verschlüsselungsverfahren im Internet zunutze: Sie lassen sich bei ausreichend hoher Schlüssellänge n nicht direkt knacken, weil dazu eine solche Faktorisierung nötig wäre und es dafür kein Verfahren gibt, mit denen ein Codeknacker in für ihn erträglicher Zeit zum Ziel käme. Was hier hingegen einfach bleibt – das heißt, mit einem P-Verfahren zu bearbeiten – das ist die Prüfung einer Lösung: Präsentiert man dem Computer einen mutmaßlichen Primfaktor der Inputzahl, ist es ihm ein Leichtes zu erkennen, ob es tatsächlich ein Primfaktor des Inputs ist. Eine schlichte Division genügt.

          Mit den Problemen in den grünen Mengen werden Computer leicht fertig. Schon bei den gelben läuft die Rechenzeit schnell aus dem Ruder - und zwar grundsätzlich, sofern der jetzt vorgelegte Beweis stimmt (links). Andernfalls könnten Computer vielleicht doch viel mehr (rechts).

          Solche Probleme, deren Lösungen polynomial schnell zu prüfen sind, bilden die Klasse NP. Das Kürzel steht aus historischen Gründen für „nichtdeterministisch polynomial“ und nicht etwa für „nicht-P“. Denn wenn Outputs von P-Algorithmen polynomial schnell generiert werden, sind sie natürlich auch polynomial schnell zu prüfen. P ist also eine Teilmenge von NP.

          Gälte P=NP wäre die Welt eine ganz andere.

          Die Frage ist aber: Könnte es nicht sein, dass schnelle Prüfbarkeit der Lösung immer eine schnelle Lösbarkeit des Problems bedeutet, auch wenn das entsprechende Lösungsverfahren, der Algorithmus, noch nicht gefunden wurde? Dann läge auch NP in P, die beiden Klassen wären also identisch: P=NP. Kein Mensch weiß, ob das so ist. Aber damit weiß auch niemand, dass es nicht so ist.

          Der heutige Wissensbestand legt zwar nahe, dass P≠NP, und die gesamte Weltwirtschaft beruht darauf, insoweit sie ohne sichere Verschlüsselung nicht mehr funktionieren würde. Aber es könnte sein, dass P=NP. Und dann wäre die Welt ein ganz anderer Ort.

          Weitere Themen

          Vertrauen und Zusammenarbeit Video-Seite öffnen

          Putin und Trump : Vertrauen und Zusammenarbeit

          Donald Trump und Wladimir Putin zogen ein positives Fazit aus ihrem Gespräch in Helsinki. Für die Lösung vieler aktueller Probleme gelte, so der Tenor des Treffens, gemeinsame Interessen entschieden und in engerem Dialog zu verfolgen.

          Topmeldungen

          Handelsstreit : Auge um Auge, Zoll um Zoll

          Handel hilft allen – doch nicht alle sehen das so. Der aktuelle Streit zwischen Donald Trump, der EU und China bedroht den Wohlstand überall auf der Welt. Hier sind die Fakten.

          Debatte über Rettungseinsätze : Feuer und Wasser

          Welche Antworten man bekommt, hängt auch in Diskussionen über Migration, Notstand und Medien von den Fragen ab, die man stellt. Je einfacher und blöder die Fragen und die Formate sind, desto schlimmer werden die Antworten.

          Studie zu Autoklischees : Jeder Popel fährt ’nen Opel

          Wackeldackel im Mercedes, drängelnde BMWs: Eine neue Studie hat die Fahrer-Klischees von Automarken untersucht. Mit der Realität stimmt das nicht immer überein.

          Newsletter

          Immer auf dem Laufenden Sie haben Post! Abonnieren Sie unsere FAZ.NET-Newsletter und wir liefern die wichtigsten Nachrichten direkt in Ihre Mailbox. Es ist ein Fehler aufgetreten. Bitte versuchen Sie es erneut.
          Vielen Dank für Ihr Interesse an den F.A.Z.-Newslettern. Sie erhalten in wenigen Minuten eine E-Mail, um Ihre Newsletterbestellung zu bestätigen.