Mathematik

Die Macht des Nein

Von Ulf von Rauchhaupt
 - 09:00
zur Bildergalerie

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

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⊃2;. Dieses n⊃2; 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⊃3; anwächst, oder n⊃1;⁰ oder n⊃3;+ n⊃2;. 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.

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.

Dann wäre einerseits die Kommunikation nicht mehr sicher. Darauf hat der Mathematiker John Nash bereits 1955 die amerikanische National Security Agency hingewiesen – 16 Jahre bevor das P=NP-Problem (das natürlich genauso gut auch P≠NP-Problem heißen könnte) formal streng gestellt wurde. Andererseits würden effiziente Algorithmen möglich, um etwa die Faltung von Proteinen vorherzusagen, was die Medizin revolutionieren würde. Optimierungsaufgaben in Industrie und Forschung, allerdings auch im Militär, Wettervorhersagen, künstliche Intelligenz: Überall wo NP-Probleme drinstecken, wären Fortschritte möglich, deren Konsequenzen für den Alltag sich vielleicht nicht einmal Science-Fiction-Autoren recht vorstellen können. Ein Beweis, dass P=NP ist, würde die Tür dazu zunächst einmal nur theoretisch aufstoßen, aber das Wissen um die prinzipielle Machbarkeit sehr wahrscheinlich enorme Energien freisetzen, die effizienten Algorithmen dann auch zu finden.

Mathematik, die sich selbst abschafft

Die Implikationen von P=NP wären aber noch weitreichender: 1956, ein Jahr nach Nashs Brief an die NSA, schrieb Kurt Gödel, wohl der bedeutendste Logiker seit Aristoteles, seinem Kollegen John von Neumann einen Brief, in dem er eine geradezu unheimliche Konsequenz von P=NP für die Mathematik selbst erkannte: „Es würde klar bedeuten ..., dass die geistige Arbeit eines Mathematikers im Fall von Ja-Nein-Fragen völlig durch Maschinen ersetzt werden könnte.“ Wer N=NP beweist, könnte theoretisch auch einen Algorithmus finden, der formale Beweise anderer mathematischer Theoreme findet – inklusive jener, die Gegenstand der sechs noch ausstehenden Millenniums-Probleme sind. Statt einer kassierte er dann sechs Millionen Dollar.

Norbert Blums Beweis vom 11. August kommt nun zu dem einerseits beruhigenden andererseits langweiligeren Schluss, dass P≠NP ist. Nur: Hat er recht?

Die kurze Antwort ist, dass die 38 Seiten lange Arbeit erst einmal von Fachleuten geprüft werden muss, was dauern kann. Zwar trafen sich gerade in der Woche, als Blum seine Arbeit ins Internet stellte, Alexander Razborov und andere in diesem Gebiet tätige Forscher am Mathematischen Forschungszentrum Oberwolfach im Schwarzwald zu einem Workshop. Doch Razborov ist nicht bekannt, dass sich unter den Teilnehmern jemand den Beweis schon genauer angeschaut hat. „Dazu muss man wissen, dass wir ein strammes Programm hatten“, sagt er. Es blieb beim Abschluss von Wetten.

Dass Problem mit den Cliquen

Dabei geht Blum das Problem von bekannter Seite an: über das sogenannte Clique-Problem. Dazu stelle man sich eine Schule mit sehr vielen Schülern vor, von denen ein jeder andere kennt, aber nicht jeder jeden. Nun gibt man die Liste der paarweisen Bekanntschaften an einen Computer mit der Aufgabe, herauszufinden, ob es eine Gruppe aus n Schülern gibt, die sich alle untereinander kennen. Dieses Problem ist NP und gehört sogar zu einer Klasse von Problemen, die man NP-vollständig nennt. Diese sind NP und zugleich „NP-schwer“, was bedeutet, auf ein solches kann jedes andere Problem in NP mit polynomialem Aufwand zurückgeführt werden. Ein Beweis, dass auch nur ein NP-vollständiges Problem in Wahrheit auch in P liegt würde damit sofort P=NP beweisen – und der Beweis, dass es nicht in P sein kann, bewiese P≠NP.

Unbenanntes Dokument

Die neue digitale Zeitung F.A.Z. PLUS

Die ganze F.A.Z. in völlig neuer Form, mit zusätzlichen Bildern, Videos, Grafiken, optimiert für Smartphone und Tablet. Jetzt gratis testen.

Nun lassen sich Algorithmen auf formale Schaltungsnetzwerke aus den logischen Verknüpfungen „und“, „oder“ sowie der Negation abbilden und zeigen, dass die Zahl der nötigen Verknüpfungen nur polynomial mit dem Input wächst, wenn auch der ursprüngliche Algorithmus das tut. Alexander Razborov bewies 1985, damals als Doktorand in Moskau, dass die Clique-Aufgabe nicht mittels polynomial mit dem Input wachsender Netzwerke bewältigt werden kann, sofern diese nur „und“ und „oder“-Verknüpfungen enthalten. Blum behauptet nun, die Beweismethode so angepasst zu haben, dass Razborovs Theorem für alle Netzwerke gilt, also auch für solche mit Negationen. Was bedeutet: Clique ist nie und nimmer in P - und infolge der NP-Vollständigkeit des Clique-Problems gilt P≠NP.

Obwohl dies dem entspricht, was die meisten theoretischen Informatiker heute glauben, überwiegt derzeit die Skepsis. Dass das „Nein“ – die Hinzunahme von Negationen in Schaltnetzwerken – diese Macht haben soll, wird vielleicht auch deswegen bezweifelt, weil diese Option den Fachleuten schon lange vor Augen gestanden haben muss. Einem Mathematiker, der sich im Internet zu dem Thema äußerte, ist Blums Beweis gewissermaßen zu konventionell, lasse zu wenig das Beschreiten völlig neuer Wege erkennen, das man von dem Beweis eines Theorems erwarten würde, an dem sich schon so viele Experten die Zähne ausgebissen haben. Hätte da Alexander Razborov in Oberwolfach dann nicht einen höheren Einsatz riskieren können? „Die Wette war 1:1000“, sagt er. „Und mein Kollege gab mir die 20 Cent sofort. Das kann man als Hinweis darauf deuten, wie er die Chance einschätzt.“

Quelle: F.A.S.
Autorenporträt / Rauchhaupt, Ulf von (UvR)
Ulf von Rauchhaupt
verantwortlich für das Ressort „Wissenschaft“ der Frankfurter Allgemeinen Sonntagszeitung.
TwitterGoogle+
  Zur Startseite
Ähnliche ThemenNSAUniversity of ChicagoDollarMathematik