• Drucken
• Senden
• Feedback

27.08.2010

Probleme haben wir Menschen eigentlich genug: Klimawandel, Artensterben, Kriminalität, Euroschwäche... Mathematiker haben diesen mitunter handfesten Schwierigkeiten ihre ganz eigenen hinzugefügt.

Etwa das Problem des Handlungsreisenden: Wie macht ein Vertreter eine möglichst kurze Rundreise durch hundert Städte?

Oder dies: Wie zerlegt man eine große Zahl schnell in ihre Primzahlteiler? Eine Aufgabe, die beim Knacken der RSA-Verschlüsselung gelöst werden muss, mit der zum Beispiel E-Mails chiffriert sind.

Mathematiker wären freilich keine Mathematiker, wenn sie Probleme nicht auch penibel klassifizieren würden. Die einfacheren Aufgaben bezeichnen sie mit P, die ganz dicken Bretter mit NP. Das entscheidende Unterscheidungsmerkmal ist der Aufwand zum Lösen des Problems: Je mehr Rechenschritte ein Computer benötigt, desto schwieriger ist die Aufgabe.

Viele Mathematiker und Informatiker glauben, dass sich komplizierte NP-Probleme nicht in leichtere P-Probleme überführen lassen. Der Beweis dafür ist allerdings noch niemandem geglückt. Dabei hat die Clay Foundation das P-NP-Problem sogar zur Milleniumaufgabe erklärt und immerhin eine Million Dollar für die Lösung ausgesetzt. Denn die Frage nach P und NP gehört zu den schwierigsten, bislang nicht gelösten Rätseln der Mathematik.

Entsprechend groß war das Aufsehen, als der indische Mathematiker Vinay Deolalikar nun Anfang August einen Beweis vorstellte. Demnach sollte tatsächlich P ungleich NP gelten. Große mathematische Probleme müssten demnach für immer große Probleme bleiben, egal wie man sie dreht und wendet.

Doch der Beweis ist offenbar lückenhaft - das hat sich in den vergangenen Wochen herausgestellt. Dick Lipton, Informatikprofessor am Georgia Institute of Technology in Atlanta, hat die Einwände und Bemerkungen verschiedener Mathematiker aus der ganzen Welt in seinem Blog dokumentiert. In einem eigens erstellten Wiki diskutieren Forscher den Beweis, den Lipton mittlerweile nur noch in ironisch-distanzierende Anführungsstriche setzt. Das Fazit Liptons und anderer Kollegen wie Neil Immerman: Deolalikars Ansatz funktioniert so nicht.

Auch auf dem Kongress der International Mathematical Union, der gerade im indischen Hyderabad stattfindet, überwiegen die Zweifel. "Dass der Beweis nicht stimmt, davon gehen hier alle Teilnehmer aus, mit denen ich gesprochen habe", sagt der Berliner Mathematiker Günter Ziegler.

Bleiben dicke Bretter immer dick?

Das Thema selbst ist kompliziert. Nur wenigen Mathematikern erschließt sich das Dutzende Seiten lange Papier des Inders Deolalikar. Was P- und NP-Probleme sind und was sie unterscheidet, kann man allerdings auch als mathematischer Laie verstehen.

Ein typisches P-Problem ist das folgende: Eine bestimmte Anzahl natürlicher Zahlen, sagen wir k, soll der Größe nach sortiert werden. Wie macht man das am einfachsten? Zunächst sucht man sich die kleinste Zahl. Dies erfordert k Schritte, denn man muss sich alle k Zahlen einzeln anschauen. Danach wiederholt sich das Verfahren mit k-1 Zahlen, bis die zweitkleinste gefunden ist, danach mit k-2 Zahlen und so weiter und so fort. Insgesamt kommen so k + (k-1) + (k-2) + ... + 2 + 1 Schritte zusammen - also 1/2*(k² + k).

Wenn sich die Menge der Zahlen k erhöht, dann braucht man natürlich länger zum Sortieren. Die Zahl der Rechenschritte steigt nicht linear (k), sondern proportional zum Quadrat (k²). Das klingt dramatisch, aber bei NP-Problemen geht es noch viel ärger zu.

Beispiel Primzahlzerlegung: Wie viele Rechenoperationen sind nötig, um einen Teiler einer großen natürlichen Zahl zu finden, von der man nur weiß, dass sie keine Primzahl ist? Das ist eine schwierige Aufgabe, denn man sieht Zahlen wie 128.927 ihre Teiler nicht an. (Es sind die Primzahlen 229 und 563.) Wer die Teiler finden will, muss nacheinander alle Zahlen von 2 bis zur Quadratwurzel von 128.927 ausprobieren.

Neue Komplexititätstheorie nötig

Die Zahl der Rechenschritte ist also so groß wie die Wurzel aus der gegebenen Zahl. Bei einer k-stelligen Zahl, die die Größenordnung 10^k besitzt, benötigt man demnach 10^k/2 Rechenoperationen, denn die Wurzel aus 10^k ist genau 10^k/2. Die nötigen Rechenschritte erhöhen sich also nicht in der zweiten Potenz wie beim Sortieren von Zahlen, sondern exponentiell.

Exponentiell oder quadratisch - das ist für große k ein dramatischer Unterschied. Die Primteilersuche ist für Mathematiker deshalb ein sogenanntes NP-Problem - zumindest solange, bis jemand einen schlauen Weg findet, um die Rechnung radikal zu verkürzen.

Geheimdienste hätten an einer solchen Abkürzung großes Interesse. Sie würde das Knacken verschlüsselter Botschaften extrem erleichtern, denn viele Verschlüsselungsverfahren beruhen darauf, dass die Primzahlen geheim sind, mit denen der Schlüssel generiert wird.

Das Verrückte an NP-Problemen ist übrigens: Eine Lösung zu finden ist sehr schwierig. Zu überprüfen, ob sie richtig ist, ist hingegen vergleichsweise leicht. Im Falle der Primzahlzerlegung multipliziert man einfach die Zahlen miteinander und schaut, ob dabei die Ausgangszahl herauskommt. Die Clay-Foundation beschreibt P-Probleme deshalb als einfach zu lösen, und NP-Probleme als einfach zu überprüfen.

Auch wenn die meisten Mathematiker glauben, dass NP-Probleme sich nicht zu P-Problemen vereinfachen lassen - ausgeschlossen ist nicht, dass es vielleicht doch geht. "Dann müsste man eine neue Komplexititätstheorie aufbauen", sagt der Mathematikprofessor Günter Ziegler. In diesem Fall wäre auch die Zerlegung natürlicher Zahlen in ihre Faktoren "zumindest theoretisch einfach. Ob sie auch praktisch einfacher wäre, weiß niemand".