Ist das zweite der sieben Millenniums-Probleme geknackt?
Ein deutscher Mathematiker hat angeblich eines der wichtigsten Probleme der Mathematik gelöst. Behält er recht, winkt ihm eine Million Dollar. Allerdings ist er nicht der erste, der das behauptet.
(Bild Science4all)
Eines der wichtigsten unbewältigten mathematischen Rätsel steht möglicherweise vor der Lösung. Es handelt sich um das sogenannte «P versus NP»-Problem aus der Informatik, das vor allem für die Kryptografie immense Bedeutung hat. Mit einer vor wenigen Tagen ins Internet gestellten Arbeit hat der Informatikprofessor Norbert Blum von der Universität Bonn möglicherweise den Beweis erbracht, dass P ungleich NP ist. Sollte sich der Beweis als korrekt und lückenlos herausstellen, könnten Kryptografen aufatmen, denn dann wären die gängigen Verschlüsselungsmethoden, die zum Beispiel für das Online-Banking und zur Bezahlung von Internetkäufen verwendet werden, weiterhin sicher.
Üppiges Preisgeld
Dem Autor der Arbeit winkt ein Preis von einer Million Dollar, den die amerikanische Clay Foundation auf die korrekte Lösung der sieben Millennium-Probleme ausgesetzt hat. Dazu muss sein Beweis allerdings noch überprüft und bestätigt werden. Denn in der Vergangenheit wurde schon mehrfach fälschlich behauptet, das «P versus NP»-Problem sei gelöst worden. Von den sieben Millennium-Problemen ist bisher nur eins, nämlich die Poincaré-Vermutung, gelöst. Der Coup gelang vor 14 Jahren dem russischen Mathematiker Grigori Perelman.
Beim «P versus NP»-Problem handelt es sich um eine Frage aus dem Gebiet der Komplexitätstheorie. Dabei geht es darum, ob mathematische Aufgaben mittels Computer innert nützlicher Frist gelöst werden können. Es ist offensichtlich, dass der Rechenaufwand zur Lösung einer mathematischen Aufgabe mit dem Umfang der Aufgabe wächst. Die Frage stellt sich: wie schnell? Zum Beispiel wächst der Rechenaufwand, um zwei Zahlen mittels eines simplen Algorithmus miteinander zu multiplizieren, etwa mit dem Quadrat der Anzahl Stellen der beiden Zahlen. Multiplikation und andere arithmetische Operationen wachsen somit polynomartig und gehören damit zur Klasse P; das heisst, sie können innert nützlicher Zeit gelöst werden.
Andere Aufgaben wachsen viel schneller als bloss polynomartig. Zum Beispiel nimmt der Rechenaufwand, um eine Zahl in ihre Primfaktoren zu zerlegen (zum Beispiel die Zerlegung der Zahl 35 in 5 und 7) exponentiell mit der Länge der Zahl zu. Das heisst, auch die schnellsten Computer können Primfaktoren mit den derzeit bekannten Algorithmen nicht in absehbarer Zeit finden, wenn die zu zerlegende Zahl genügend gross ist. Da zur Verschlüsselung von Kreditkartennummern im Internet routinemässig Zahlen mit 256 Stellen benützt werden, scheint die Chiffriermethode vor Computerangriffen sicher zu sein. Aber ganz sicher ist man da nicht.
Überprüfen ist einfacher als lösen
Mathematische Probleme der Klasse NP sind eine Untergruppe der schwer zu lösenden Aufgaben. Es sind Aufgaben, bei denen – wenn man einmal einen Lösungsvorschlag hat – relativ rasch festgestellt werden kann, ob der Vorschlag richtig ist. Bei der Primfaktorenzerlegung muss man die vorgeschlagenen Faktoren nur miteinander multiplizieren (der Rechenaufwand nimmt dann bloss mit dem Quadrat der Ziffern zu), um zu verifizieren, dass diese Zahlen tatsächlich die gesuchten Primfaktoren sind.
«P versus NP» fragt, ob die NP-Probleme letztlich genauso harmlos sind wie die P-Probleme. Oder anders ausgedrückt: Sind Probleme, deren Lösungen einfach überprüft werden können, im Prinzip auch einfach zu lösen? Sollte diese Frage bejaht werden, müsste bloss noch der geeignete Algorithmus gefunden werden, um auch NP-Probleme innert nützlicher Zeit zu lösen. Für die Kryptografie wäre dies eine Katastrophe. Da die Zerlegung einer Zahl in ihre Primfaktoren zur Klasse der NP-Probleme gehört, ist nicht ausgeschlossen, dass die gängigen Verschlüsselungsmethoden unsicher sind. Möglicherweise haben Nachrichtendienste oder Computer-Hacker solche Algorithmen sogar schon gefunden, halten sie aber geheim.
Blum verneint in seinem 38-seitigen Beweis diese Möglichkeit. Falls ihm keine Fehler unterlaufen sind, ist NP ungleich P ist. Dies würde nicht nur bedeuten, dass noch keine Algorithmen zur effizienten Primzahlzerlegung gefunden wurden, sondern dass es solche Algorithmen schlichtweg nicht gibt.
Folgen Sie der Wissenschaftsredaktion der NZZ auf Twitter.
