Mathematische Probleme Das Komplizierte ist unfassbar

Steckt hinter jedem schwierigen Problem vielleicht ein einfaches? Mathematiker treibt diese Frage schon viele Jahre um, ein Inder wollte nun das Gegenteil beweisen - löste damit aber nur neue Debatten übers Grundsätzliche aus: Wie simpel ist die Welt zu erklären?

Von

Schwierige Sache: Ist das Problem noch P oder schon NP?
DDP

Schwierige Sache: Ist das Problem noch P oder schon NP?


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*(k2 + 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 (k2). 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 10k besitzt, benötigt man demnach 10k/2 Rechenoperationen, denn die Wurzel aus 10k ist genau 10k/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".

Mehr zum Thema


Forum - Diskutieren Sie über diesen Artikel
insgesamt 136 Beiträge
Alle Kommentare öffnen
Seite 1
tetaro 27.08.2010
1. Grenzen der Erkenntnis
Zitat von sysopSteckt hinter jedem schwierigen Problem vielleicht ein einfaches? Mathematiker treibt diese Frage schon viele Jahre um, ein Inder wollte nun das Gegenteil beweisen - löste damit aber nur neue Debatten übers Grundsätzliche aus: Wie simpel ist die Welt zu erklären? http://www.spiegel.de/wissenschaft/mensch/0,1518,713386,00.html
Der Versuch, alle Probleme auf etwas Simples zurückzuführen, wird deshalb nichtmöglich sein, da wir (als denkende Wesen) nicht über die Beschränkungen unserer biologischen Hardware hinauswachsen können. Jede Sichtweise wird also eine Subjektive Verfärbung enthalten, die wiederum zu irgendwelchen komischen Denk-Rekursionen führen kann. Der objektive Blickpunkt ist technisch gesehen nicht zu erreichen. Die Fehler und Grenzen eines Dreijährigen bei der Weltbetrachtung kann nur ein Älterer erkennen, aber nicht der Dreijährige selbst. Wollte er über seine Beschränkungen hinausgehen, wird er sich irgendwo heillos in diesen Grenzen verstricken. Genauso geht es uns vermutlich bei unserer eigenen Theoriebildung im Verhältnis auf fortgeschrittenere Betrachtungsweisen.
firelala 27.08.2010
2. Ob Faktorisierung in liegt NP ist offen!
Das Beispiel für ein NP-Problem ist denkbar ungünstig gewählt, da es nicht bekannt ist ob die Faktorisierung in NP liegt oder nicht. Da es einen Sub-Exponentialzeitalgorithmus gibt (Zahlenkörpersieb) ist die Laufzeit um RSA zu brechen sehr viel geringer als 2^O(n). Außerdem liegt das Problem in QP, der Klasse aller mit Quantencomputern effizient lösbaren Probleme, von der man wiederherum nicht weiß ob diese Klasse mit P übereinstimmt oder mit NP oder dazwischen liegt. Viele ähnliche Fragestellungen sind auch noch offen. Ein sehr viel sinnvolleres und auch anschaulicheres Beispiel wäre das Problem das Handlungsreisenden gewesen: Ein Handlungsreisender will n Städte besuchen und sucht eine Route um alle Städte zu besuchen. Die "NP-Frage" ist nun: Gibt es eine Route die kürzer ist als x? Für eine exakte Lösung ist kein effizienter Algorithmus (d.h. Polynomialzeit) bekannt! Insgesamt ist es interessant über solche Dinge auch mal auf Spiegel Online zu lesen. Aber wenn, dann sollte man auch korrekt recherchieren.
Flutsch, 27.08.2010
3. Mathematische Philosophie
Zitat von tetaroDer Versuch, alle Probleme auf etwas Simples zurückzuführen, wird deshalb nichtmöglich sein, da wir (als denkende Wesen) nicht über die Beschränkungen unserer biologischen Hardware hinauswachsen können. Jede Sichtweise wird also eine Subjektive Verfärbung enthalten, die wiederum zu irgendwelchen komischen Denk-Rekursionen führen kann. Der objektive Blickpunkt ist technisch gesehen nicht zu erreichen. Die Fehler und Grenzen eines Dreijährigen bei der Weltbetrachtung kann nur ein Älterer erkennen, aber nicht der Dreijährige selbst. Wollte er über seine Beschränkungen hinausgehen, wird er sich irgendwo heillos in diesen Grenzen verstricken. Genauso geht es uns vermutlich bei unserer eigenen Theoriebildung im Verhältnis auf fortgeschrittenere Betrachtungsweisen.
Es ist interessant, dass sie eine intrinsische Grenze aufzeigen. Halten Sie es für möglich, dass eine Grenze des Verstehens deshalb nicht bemerkt werden wird, da sie nicht nur in unserer Biologie, sondern fest im Universum kodiert ist? Sind Universen denkbar, in denen die Primzahlen nicht 1,3,5,7,11,13,... lauten, sondern anders verteilt sind? Damit wären wir naturgemäß nicht in der Lage, beliebig weit in die "Meta-Ebene" zu springen, in der wir Aussagen über die Lösbarkeit von Problemen machen. Das mathematische Universum gliche dann einer Kugel, auf deren Oberfläche wir leben. Die Kugel ist offenbar begrenzt, wir können als Oberflächenwesen jedoch keine Grenzen feststellen. Dies würde bedeuten, dass wir nur prinzipiell sagen könnten, dass etwas nicht mit unseren Werkzeugen lösbar ist, mehr aber auch nicht. Andere Werkzeugkoffer stehen in anderen Universen (vielleicht) und sind uns nicht zugänglich.
bnn 27.08.2010
4. ?
Irgendwas stimmt hier nicht. Das sortierproblem habe ich verstanden: k Zahlen, Anzahl Rechenschritte ist proportional zu kˆ2. Wenn es aber stimmt, dass die Anzahl der Rechenschritte fuer die Primzahlzerlegung k^1/2 ist, so ist das Primzahlproblem bezueglich k natuerlich einfacher zu loesen. Scheinbar wird gemeint, dass die Frage ist, wie schwierig es ist, eine k-stellige Zahl primzahlzuzerlegen. Dann gibt es die exponentielle Schwierigkeit. Dann wuerde aber auch das Sortierproblem bei (10^k)^2 liegen, also wuerde dies noch haerter sein als das Primzahlproblem...
Fackus 27.08.2010
5. Praxis !
Man könnte die Vereinfachung ja zuerst mal an praktischen Fragestellungen ausprobieren. Deutsches Steuerwesen zum Beispiel. Da liesse sich aus dem np schon ein p machen, wenn man denn nur wollte. Und dann zerpflücke man den restlichen Gesetzesmüll bis man wieder auf p = die 10 Gebote ist.
Alle Kommentare öffnen
Seite 1

© SPIEGEL ONLINE 2010
Alle Rechte vorbehalten
Vervielfältigung nur mit Genehmigung der SPIEGELnet GmbH


Die Homepage wurde aktualisiert. Jetzt aufrufen.
Hinweis nicht mehr anzeigen.