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

          Topmeldungen

          Brexit-Verhandlungen : Ohne Qualen geht es nicht

          Theresa May flehte diese Woche in Berlin, Paris und Brüssel um Hilfe bei den Brexit-Verhandlungen. Die Europäer blieben hart. Aber sie gaben sich Mühe, nett zu sein.
          Erst mal shoppen in der Stadt, dann zu Hause noch bei Zalando bestellen.

          Geld in der Partnerschaft : Hilfe, meine Frau wirft das Geld raus!

          In Gelddingen zeigt sich oft die Wahrheit über eine Beziehung, sagen Paartherapeuten. Aber wer wird denn gleich an Scheidung denken, wenn die Ehepartnerin über die Verhältnisse lebt?
          Für mehr Recht und Ordnung im eigenen Land: Macron will härter gegen kriminelle Ausländer vorgehen.

          Macrons Abschiebekurs : Mit harter Hand

          Der brutale Mord an zwei jungen Frauen durch einen illegalen Einwanderer erschüttert Frankreich. Nun plant Präsident Macron konsequenter bei der Abschiebung krimineller Ausländer durchgreifen. Doch die Umsetzung gestaltet sich schwerer als gedacht.

          SPD : Der wahre Sieger der Bundestagswahl

          So ein bisschen freuen sich die Sozialdemokraten über das katastrophale Ergebnis der Bundestagswahl. Endlich sind sie die Union los. In der Opposition soll alles besser werden.

          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.