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).
          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). : Bild: F.A.Z. Grafik Piron

          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

          Der Trip der alten Gräfin Video-Seite öffnen

          LSD als Allheilmittel? : Der Trip der alten Gräfin

          Amanda Feilding aus dem englischen Hochadel will beweisen, worauf nicht nur Tech-Nerds im Silicon Valley schwören: dass kleine Dosen LSD kreativ machen – und Depressionen vertreiben können.

          Ich war am Ende nur noch ein Wrack Video-Seite öffnen

          Video-Serie „Frankfurt & ich“ : Ich war am Ende nur noch ein Wrack

          Seit über zehn Jahren ist Thomas Adam trocken und erzählt auf Stadtführungen durch sein ehemaliges „Sauf- und Bettelgebiet“ seine Geschichte von der Straße. FAZ.NET hat Adam für die Video-Serie „Frankfurt & ich“ begleitet.

          Topmeldungen

          Bundeskanzlerin Angela Merkel und SPD-Chef Martin Schulz im Bundestag

          Umfrage : Große Koalition gewinnt an Zustimmung

          Eine große Koalition aus Union und SPD findet Umfragen zufolge deutlich mehr Zustimmung bei den Deutschen als noch vor einer Woche. Am Freitag entscheidet die SPD-Führung, ob sie Sondierungen aufnehmen möchte.

          Brexit-Veto : Ein erster Sieg im Rückzugsgefecht

          Nach Mays Niederlage im Parlament keimt nun bei vielen die Hoffnung auf, dass die Regierung gezwungen sein könnte, in Brüssel einen „weicheren“ Brexit zu verhandeln. Ein Rennen gegen die Zeit.

          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.