Die Sieben-Millionen-Dollar-Probleme
Sie wurden am 24. Mai 2000 in einem Festakt in Paris ausgelobt, anwesend waren einige
der zurzeit prominentesten Mathematiker. Der Ort hatte einen
symbolischen Charakter: Anlässlich des Weltkongresses der
Mathematiker
im Jahr 1900 stellte der berühmte Mathematiker David
Hilbert
23 schwierige
Probleme
vor,
die Beschäftigung mit dieser Herausforderung
hat die Mathematik im vorigen Jahrhundert wesentlich beeinflusst.
Daher also musste es Paris sein, wieder sollen durch die Konzentration
auf wenige Fragen Akzente für die Forschung gesetzt werden.
(Etwas vollmundiger als 1900 sollten es diesmal nicht nur Probleme
für ein Jahrhundert, sondern gleich für ein Jahrtausend
sein.)
Auslober des Preises ist die
Clay Foundation,
eine über erhebliche
Mittel verfügende Organisation, die
schon seit mehreren Jahren mit bemerkenswertem Einsatz für die Förderung der
Mathematik aktiv ist. Die Preise wurden von einem Gremium einiger der besten
Mathematiker der Welt ausgewählt, sie betreffen Probleme der reinen Mathematik
und der Anwendungen von Mathematik.
Es folgt nun der Versuch, einige dieser Probleme zu beschreiben. die vollständige
Liste findet man auf der Seite der Clay Foundation.
Die Riemannsche Vermutung
Dabei geht es um eine seit 150 Jahren offene Frage, die von dem deutschen
Mathematiker Bernhard
Riemann formuliert wurde.
Um das Problem
für Laien zu beschreiben, muss man an die Definition des Begriffs "Primzahl"
erinnern: Eine natürliche Zahl n heißt Primzahl,
wenn sie nur durch 1 und durch sich selbst teilbar ist.
3, 17, 101 sind Beispiele für Primzahlen, 99 dagegen ist keine.
Nun kennt man seit etwa 100 Jahren eine Näherungsformel für die Anzahl der
Primzahlen. Sie wurde schon von
Gauß vermutet, bewiesen wurde sie
aber erst 1896 von den Franzosen
Hadamard
und (unabhängig)
de la Vallée Poussin. Durch die Formel
wird ausgesagt, dass es - für große Zahlen x - unterhalb von x
ungefähr
viele Primzahlen gibt (dabei ist der natürliche Logarithmus von x der Logarithmus von x zur Basis e, also diejenige Zahl y, für die ey=x gilt). Damit hat man zum Beispiel die grobe Information, dass etwa ein Zehntel der Zahlen unterhalb 22.000 Primzahlen sind, denn der natürliche Logarithmus von 22.000 ist ungefähr 10. Und die Riemannsche Vermutung lässt sich dann formulieren als Formel für eine wesentlich bessere Näherung. Statt des Logarithmus tritt hier der Integrallogarithmus auf, die genaue Formulierung ist ziemlich technisch.
Etwas präziser kann die Riemannsche Vermutung so umformuliert werden, dass sie der Voraussage derjenigen Punkte entspricht, an denen eine gewisse Funktion den Wert Null annimmt. Diese Funktion - die Riemannsche Zetafunktion - ist zunächst durch die folgende Zuordnung definiert: Einer Zahl x, die größer als 1 ist, wird der Wert
zugeordnet. Nun kann man die Definition dieser Funktion auf alle von 1 verschiedenen komplexen Zahlen erweitern, und es geht um die Nullstellen dieser Fortsetzung.
Die Poincaré-Vermutung
Stellen Sie sich die Kugeloberfläche vor.
Wenn man dort eine geschlossene Kurve zeichnet
und sie sich als ausgelegten Bindfaden vorstellt, so ist dieser stets zu
einem Punkt zusammenzuziehen, ohne dass der Bindfaden die Kugeloberfläche
verlässt.
Nicht alle geschlossenen Flächen haben diese Eigenschaft: Auf dem Torus (das ist
die mathematische Bezeichnung für einen Rettungsring) kann man einen Faden
einmal so herumschlingen, dass er nicht zusammengezogen werden kann.
Es ist nun schon lange bekannt, dass die Kugeloberfläche sogar das
einzige Beispiel ist: Kann auf einer geschlossenen Fläche F jede Kurve
zusammengezogen werden, so ist F im Wesentlichen (d.h., bis auf Verzerrungen)
gleich der Kugeloberfläche.
Bei der
Poincaré-Vermutung geht es um das entsprechende Ergebnis,
wenn die Dimension um eins erhöht wird.
Etwas lax formuliert, kann man sie wie folgt formulieren.
Für eine Welt, die von jeder Stelle aus
gesehen im Kleinen so aussieht wie der uns umgebende dreidimensionale
Raum, die keine Ränder hat, "nicht zu groß" ist und in der jede Kurve zusammengezogen
werden kann, gibt es im Wesentlichen nur einen einzigen Kandidaten:
die dreidimensionale Oberfläche der vierdimensionalen Kugel.
Kein Mensch weiß heute, ob das stimmt. Für den Beweis oder das Finden
eines Gegenbeispiels könnte man um 1.000.000 Dollar reicher werden.
Obige Formulierung ist, zugegeben, nicht ganz präzise. Auch ist ohne etwas Phantasie eine vierdimensionale Kugel nicht leicht vorstellbar. Aber: Für die mathematisch strenge Version benötigt man Kenntnisse, die man üblicherweise erst nach einigen Semestern Studium hat.
Man sollte noch betonen, dass das Problem deswegen interessant ist, weil man unsere wirkliche Welt als dreidimensionales Gebilde in einer vierdimensionalen Raum-Zeit-Welt auffassen kann.
Wer alles etwas ausführlicher nachlesen möchte, kann das in dem Artikel "Die Geometrie der Welt" von Martin Aigner in dem Buch "Alles Mathematik" tun.
Im Jahr 2002 bewies der russische Mathematiker Grigori Perelman die Poincaré-Vermutung. Inzwischen ist der Beweis allgemein anerkannt.
P=NP
Hier geht es, etwas pathetisch ausgedrückt, um die Grenzen des Wissens.
Mathematiker wollen doch konkrete Probleme lösen: Man gibt gewisse
Werte ein, rechnet eine Weile, und dann erhält man die Lösung. Es hat
sich als günstig erwiesen,
als einfach solche Probleme anzusehen, bei denen die
Rechenzeit nicht zu stark mit der Problemgröße wächst. Genauer:
Braucht man n Ziffern, um das Problem zu beschreiben, so soll
die Rechenzeit durch
eine feste Potenz von n abschätzbar sein. Nehmen wir zum Beispiel
das Multiplizieren n-stelliger Zahlen.
Da muss man im Wesentlichen n2
Rechenoperationen durchführen, und deswegen ist Multiplizieren ein
"einfaches" Problem.
Die meisten der in der Schule behandelten Algorithmen
sind von dieser Art:
Addieren, Multiplizieren, Gleichungssysteme lösen, Wurzeln ziehen.
Der Fachausdruck dafür lautet:
Probleme vom Typ P, das "P" steht für "polynomiell".
Längst nicht alle Probleme sind einfach:
Möchte ich von einer n-stelligen Zahl wissen,
ob es sich um eine Primzahl handelt,
so ist der Aufwand nicht durch eine Potenz
von n abschätzbar. Vielmehr ist er von der Größenordnung 10n,
so viele Zahlen muss ich als potenzielle Teiler prüfen. Der Aufwand
wächst also exponentiell
mit n.
Mal angenommen, eine Zahl n ist das Produkt von zwei Zahlen:
n=p·q.
Einer dieser Faktoren soll gefunden werden. Wenn man das durch systematisches Probieren
versucht zu lösen, ist das sicher kein Problem
vom Typ P, der Aufwand wächst
wieder exponentiell mit n. Allerdings:
Wenn wir einfach einen Teiler p raten und Glück haben,
geht es ganz schnell: Wir teilen n durch p (das ist einfach!),
es geht auf, fertig.
Probleme, die sich durch mit viel Glück durch
Raten auf Probleme vom Typ P zurückführen
lassen, heißen vom Typ NP; das soll "nichtdeterministisch polynomiell"
abkürzen.
Und nun das Problem: Man gebe wenigstens eine Situation an, in der ein Problem vom Typ NP, nicht aber vom Typ P ist (oder beweise, dass alle NP-Probleme schon vom Typ P sind). Prägnant zusammengefasst wird das als
Naiv gesehen ist NP viel, viel schwieriger als P, aber bisher hat
noch niemand ein Beispiel gefunden, wo das auch streng gezeigt werden könnte.
(Im Jahr 1999 gab es einen
Artikel
in der Wochenzeitschrift "Die Zeit", in der dieses Problem
etwas ausführlicher dargestellt ist.)
