Angeblich kann man als Mathematiker nicht besonders reich werden – ein magerer Lohn gemessen an der Genialität, die das Studium zu erfordern scheint. Dabei ist die Realität gar nicht so schlecht: Die Einstiegsgehälter für Hochschulabsolventen in Mathematik liegen im oberen Bereich. Wen es allerdings nach dem ganz großen Geld gelüstet, der sollte sich nicht gerade auf abstrakte Algebra, komplex-analytische Funktionen oder Topologie stürzen.

Oder etwa doch?

Das Clay Mathematics Institute (CMI), eine gemeinnützige Stiftung mit Sitz in Cambridge (Massachusetts), bietet jeweils eine Million Dollar für die Lösung von sieben offenen Problemen der Mathematik. Die im Mai 2000 verkündeten sieben "Millennium-Preis-Probleme", wie sie das CMI nennt, gehören nach Expertenmeinung zu den wichtigsten – und schwersten – ungelösten Problemen der heutigen Zeit. Zwei der Probleme kommen aus der Zahlentheorie, zwei aus der Topologie, zwei aus der mathematischen Physik und eines aus der theoretischen Informatik.

Zeta-Funktion und die Verteilung der Primzahlen: die Riemannsche Vermutung

Das älteste Millennium-Problem betrifft die Eigenschaften der so genannten Riemannschen Zeta-Funktion, die üblicherweise durch die Formel

\zeta(s) = 1 + 1/2^s + 1/3^s + 1/4^s + ...

definiert wird (\zeta ist der kleine griechische Buchstabe zeta). Interessanterweise verwenden die Mathematiker die Zeta-Funktion nicht ernsthaft als Funktion, das heißt als Rezept, um zu einer (komplexen) Zahl s den Funktionswert \zeta(s) zu finden; der interessiert eigentlich niemanden. Vielmehr ist eine solche Funktion ein Mittel, um die Eigenschaften unendlich vieler Zahlen in handlicher Form zusammenzufassen und andere Eigenschaften daraus herzuleiten (Spektrum der Wissenschaft 10/2002, S. 100). So hatte Leonhard Euler (1707–1783) bereits 1737 beobachtet, dass die Zeta-Funktion statt als Summe auch als ein Produkt geschrieben werden kann, in dem alle Primzahlen vorkommen:

\zeta(s) = 1/(1-2^-s)(1-3^-s)(1-5^-s) ...

Davon ausgehend, untersuchte der deutsche Mathematiker Bernhard Riemann (1826–1866) mithilfe der Zeta-Funktion die Verteilung von Primzahlen und fand erstaunlich präzise Formeln für deren Verteilung: Wie viele unter den natürlichen Zahlen von 1 bis x sind Primzahlen? In einem berühmt gewordenen Aufsatz aus dem Jahr 1859 machte er Gebrauch von der damals aufkommenden komplexen Funktionentheorie, die über solche unendlichen Reihen erstaunlich weitreichende Aussagen zu treffen gestattet. Seine Analyse wurde später präzise gefasst und führte zu einem vollständigen Beweis des Primzahlsatzes: Die Anzahl der Primzahlen kleiner als x ist annähernd x / ln x (wobei ln x der natürliche Logarithmus von x ist).

In die Formeln für die Verteilung der Primzahlen gehen die Nullstellen der Zeta-Funktion ein; das sind alle (komplexen) Werte s, für die \zeta(s)=0 ist. Es gibt zwei Typen von Nullstellen: Die "trivialen" sind die negativen geraden ganzen Zahlen (s= -2, -4, -), die "nicht-trivialen" haben Realteile zwischen 0 und 1. In den letzteren stecken detaillierte Informationen über eine Funktion (das "logarithmische Integral"), welche die Anzahl der Primzahlen unterhalb von x noch weit besser approximiert als x / ln x. Riemann hielt es für "sehr wahrscheinlich", dass die Realteile der nicht-trivialen Nullstellen der Zeta-Funktion alle gleich 1/2 sind – was nichts anderes heißt, als dass sie alle auf einer Geraden liegen. Diese Vermutung Riemanns wurde als "Riemannsche Vermutung" sprichwörtlich. "Es wäre natürlich wünschenswert, einen strengen Beweis zu haben", ergänzte er.

Allerdings. Ausgedehnte Computerberechnungen haben Millionen von nichttrivialen Nullstellen der Zeta-Funktion gefunden, sämtlich mit Realteil 1/2 – aber einen Beweis gibt es bis heute nicht. Wenn die Riemannsche Vermutung wahr sein sollte – und kaum jemand zweifelt ernsthaft daran –, dann hat sie tiefgreifende Konsequenzen für die Zahlentheorie und über die Mathematik hinaus, bis hin zu einer Theorie des Quantenchaos.

Wie rational sind elliptische Kurven?

Das andere zahlentheoretische Millennium-Problem ist die Vermutung von Birch und Swinnerton-Dyer. In den 1960er Jahren führten die britischen Mathematiker Brian Birch und Peter Swinnerton-Dyer eine umfangreiche, rechnergestützte Untersuchung über die so genannten L-Funktionen elliptischer Kurven durch. Diese Funktionen sind nahe Verwandte der Riemannschen Zeta-Funktion; eine elliptische Kurve ist nicht etwa eine Ellipse, sondern eine Kurve in der Ebene, die durch eine Gleichung der Form x^3 + A x^2 + B x + C – y^2 in den beiden Variablen x und y definiert ist (wobei lineare Transformationen der Koordinaten x und y zugelassen sind und die ganzzahligen Koeffizienten A, B und C noch gewisse Zusatzbedingungen erfüllen müssen). Birch und Swinnerton-Dyer stellten fest, dass in jedem der von ihnen untersuchten Beispiele die L-Funktion L_E zu einer elliptischen Kurve E Auskunft darüber gab, ob E unendliche viele rationale Punkte (beide Koordinaten sind rationale Zahlen) hat. Und zwar war das genau dann der Fall, wenn L_E(1)=0 war. Die Vermutung von Birch und Swinnerton-Dyer besagt, dass dies allgemein gilt.

Wenn also die Funktion L_E im Punkt 1 eine Nullstelle hat, dann soll die elliptische Kurve E unendlich viele rationale Punkte haben. Und wenn L_E eine doppelte Nullstelle hat, dann sollen es "doppelt unendlich viele" rationale Punkte sein, bei einer dreifachen Nullstelle "dreifach unendlich viele" und so weiter. Das ist der gesamte Inhalt der Vermutung von Birch und Swinnerton-Dyer.

Die Schlinge zieht sich zu: die Poincarésche Vermutung

Unter den beiden Topologie-Problemen ist die Poincaré-Vermutung die berühmtere. Grob gesprochen behauptet sie, dass es ein untrügliches Kennzeichen gibt, um einen topologisch komplizierten dreidimensionalen Raum von einem einfachen zu unterscheiden. Die fachsprachliche Formulierung ist zunächst abschreckend: "Eine kompakte dreidimensionale Mannigfaltigkeit hat genau dann eine triviale Fundamentalgruppe, wenn sie homöomorph zur 3-Sphäre ist." Aber der Satz ist nicht so schlimm, wie er klingt. Schauen wir uns seine Worte der Reihe nach an.

"Homöomorph" ist eine vornehme Ausdrucksweise für "im Wesentlichen gleich", und zwar im Sinne der Topologie ("Gummituch-Geometrie"). Ein Luftballon bleibt ein Luftballon, einerlei wie man ihn deformiert – solange man keine Löcher hineinsticht, ihn nicht zerschneidet, zerreißt oder mit sich zusammenklebt. Eine Mannigfaltigkeit sieht zunächst aus wie ein gewöhnlicher euklidischer Raum, sei es eine zweidimensionale Ebene, ein dreidimensionaler Raum oder ein Gebilde höherer Dimension. Das gilt jedenfalls "lokal", das heißt wenn man nicht über die unmittelbare Umgebung seines Standpunktes hinausschaut. Eine Mannigfaltigkeit ist dreidimensional, wenn man von jedem ihrer Punkte aus in drei zueinander senkrechten Richtungen wandern kann – zumindest ein kurzes Stück weit. Zweidimensionale Mannigfaltigkeiten kann man sich noch einigermaßen vorstellen; es sind einfach gekrümmte Flächen. "Kompakt" bei einer solchen Fläche bedeutet "von begrenzter Ausdehnung"; die Kugeloberfläche ("Sphäre"), der Torus (Fahrradschlauch) und die Oberfläche einer Brezel mit beliebig vielen Löchern sind alle kompakt.

Die Fundamentalgruppe einer Mannigfaltigkeit ist eine algebraische Struktur – eben eine Gruppe –, die geschlossene Kurven auf der Mannigfaltigkeit beschreibt. Im zweidimensionalen Fall stelle man sich eine Drahtschlaufe vor, die gezwungen ist, in der Oberfläche zu liegen, aber im Übrigen beliebig bewegt, gedehnt oder zusammengezogen werden darf. Alle Kurven, die durch eine solche Deformation auseinander hervorgehen, gelten, wie in der Topologie üblich, als gleich ("äquivalent"). Die Fundamentalgruppe besteht aus allen diesen Kurven, wobei topologisch äquivalente Kurven identifiziert werden. Ein Element der Gruppe ist also eine ganze Klasse äquivalenter Kurven. Zu einer Gruppe gehört stets eine Verknüpfung (namens "Addition" oder "Multiplikation"), die aus zwei Elementen der Gruppe ein drittes macht. In diesem Fall besteht die Summe zweier Kurven aus der Kurve, die entsteht, wenn man beide Kurven hintereinander durchläuft.

Für die zweidimensionale Sphäre ist leicht zu sehen – wenn auch nicht ganz so leicht zu beweisen –, dass eine solche Schlaufe, einerlei wie kompliziert sie ist, auf einen Punkt zusammengezogen werden kann. Das ist beim Torus nicht der Fall: Eine Schlaufe, die sich einmal um den Fahrradschlauch windet oder das große Loch in seiner Mitte umrundet, lässt sich nicht zu einem Punkt zusammenziehen. Also ist die Fundamentalgruppe der 2-Sphäre "trivial", denn sie besteht nur aus einem einzigen Element, während die Fundamentalgruppe des Torus (wie auch für alle anderen komplizierteren Flächen) nicht-trivial ist. Zweimal einen Torus zu umrunden ist etwas ganz anderes als einmal.

Ganz ähnlich ist es bei den dreidimensionalen Mannigfaltigkeiten. Die Fundamentalgruppe der 3-Sphäre (der "Oberfläche der vierdimensionalen Kugel") ist trivial, die des dreidimensionalen Torus jedoch nicht. 1904 vermutete Henri Poincaré (1854–1912), dass jede dreidimensionale Mannigfaltigkeit, die nicht gerade homöomorph zur 3-Sphäre ist, eine nicht-triviale Fundamentalgruppe hat. Dies trifft auch für alle heute bekannten dreidimensionalen Mannigfaltigkeiten zu. Leider ist es sehr schwierig, über diese Gebilde einen Überblick zu gewinnen. Am schönsten wäre es, wenn man, wie im zweidimensionalen Fall, eine Klassifikation hätte: Jede zweidimensionale Mannigfaltigkeit lässt sich in eine von unendlich vielen wohlbekannten Schubladen stecken. Für dreidimensionale Mannigfaltigkeiten hat William Thurston von der Universität von Kalifornien in Davis in den 1970er Jahren eine Klassifizierung vermutet. Wenn diese "Geometrisierungs-Vermutung" bewiesen werden sollte – was bis heute nicht der Fall ist –, wäre die Poincarésche Vermutung gleich mit erledigt.

Interessanterweise wurden entsprechende Sätze für höherdimensionale Mannigfaltigkeiten bereits bewiesen, obgleich deren Klassifikation noch sehr in den Anfängen steckt. Eine n-dimensionale Mannigfaltigkeit mit n ≥ 4 hat genau dann eine triviale Fundamentalgruppe, wenn sie homöomorph zur n-Sphäre ist. Für Dimension 5 und höher wurde dies zuerst 1960 von Stephen Smale von der Universität von Kalifornien in Berkeley bewiesen. Der vierdimensionale Fall hielt bis 1982 stand, als ihn Michael Freedman von der Universität von Kalifornien in San Diego erledigte.

Warum ist ausgerechnet die dritte Dimension so schwer? Betrachten wir die Fläche, die unsere Drahtschlinge überstreicht, wenn sie zu einem Punkt zusammengezogen wird. Topologisch gesehen ist diese Fläche eine Kreisscheibe; wenn die Mannigfaltigkeit aber in einen euklidischen Raum eingebettet ist, können alle möglichen Knicke und Selbst-Überschneidungen auftreten. Dann ist die Schlaufe zwar zu einem Punkt zusammenziehbar, aber wir merken es nicht. Auf der 2-Sphäre kann einem das nicht passieren. In drei Dimensionen dagegen missrät die Schlaufe häufig zu einem unentwirrbaren Knoten. Noch in vier Dimensionen ist es manchmal unmöglich, beim Zusammenziehen Selbst-Überschneidungen zu vermeiden. Aber in fünf und mehr Dimensionen ist so viel Platz, dass man die Scheibe stets sauber auswischen kann.

Algebraische Mannigfaltigkeiten und die Hodge-Vermutung

Das andere topologische Millionen-Dollar-Problem ist die Hodge-Vermutung, benannt nach William Hodge, der sie 1950 erstmals aufgstellte. Es geht um höherdimensionale Mannigfaltigkeiten, die über Systeme algebraischer Gleichungen definiert sind. Die Vermutung sagt im Wesentlichen: Was Sie schon immer über algebraisch definierte Mannigfaltigkeiten wissen wollten, aber nicht zu fragen wagten, ist mit Mitteln der Analysis zu finden.

Eine algebraisch definierte Mannigfaltigkeit ist die Lösungsmenge eines System von Polynomgleichungen. In der Regel defniert eine Gleichung in n Variablen eine "Hyperfläche" der Dimension n-1. Zum Beispiel definiert die Gleichung x²+y²+z²=1 in drei Variablen die zweidimensionale Sphäre. Die Lösungsmenge eines Systems mit k Gleichungen ist die Schnittmenge der dazugehörigen Hyperflächen, im Allgemeinen ist sie von der Dimension n-k.

Wie eine solche Mannigfaltigkeit aussieht, kann man sich praktisch nicht mehr vorstellen, vor allem, wenn die Variablen komplexe Zahlen sind, doch die Mathematik funktioniert im Wesentlichen genauso wie im niedrigdimensionalen Fall. Insbesondere ist es möglich, auf diesen Mannigfaltigkeiten Analysis, sprich Differential- und Integralrechnung, zu treiben. Der Formalismus dazu heißt "Kohomologie-Theorie", und von zentraler Bedeutung darin ist ein Vektorraum aus Differenzialformen, der so genannte Hodge-Raum. (Ein Differenzial fdx ist das, was in dem Integral ∫_a^bf(x)dx "integriert wird". Differenzialformen sind höherdimensionale Verallgemeinerungen davon.) Die Hodge-Vermutung behauptet, dass dieser Vektorraum für jede algebraisch definierte Mannigfaltigkeit von Differenzialformen aufgespannt wird, die ihrerseits zu algebraisch definierten Untermannigfaltigkeiten gehören.

Was genau die Hodge-Vermutung aussagt, ist nicht einfach zu verstehen und noch schwieriger richtig zu formulieren. Letzteres misslang Hodge selbst bei seinem ersten Versuch! Er schlug auch eine Verallgemeinerung vor, die sich als falsch herausstellte. Das korrigierte der französische Mathematiker Alexandre Grothendieck 1969 in einem Aufsatz mit dem drastischen Titel: "Hodges allgemeine Vermutung ist aus trivialen Gründen falsch." Solche Missgriffe sind in der frühen Entwicklung eines Fachgebietes nichts Besonderes. Auch die Forscher selbst brauchen Zeit, um die beste Ausdrucksweise für ihre Entdeckungen zu finden.

Heute verstehen die Mathematiker die Theorie gut genug, um sicher zu sein, dass die Hodge-Vermutung korrekt formuliert ist, und sie halten sie allgemein für richtig. Dennoch könnte sie sich immer noch als falsch herausstellen, aus "trivialen" Gründen, die sich in den letzten 50 Jahren der Aufmerksamkeit entzogen haben. Das CMI ist ganz allgemein bereit, den ausgesetzten Preis auch für eine Widerlegung anstelle eines Beweises einer Vermutung zu vergeben – vorausgesetzt, das widerlegende Gegenbeispiel verändert radikal das Wesen der Theorie. Wenn es dagegen, wie bei Grothendieck, lediglich einen kleinen Fehler aufdeckt, behält sich das CMI das Recht vor, das Problem neu zu stellen. (Da es um größere Beträge geht, hat das CMI seine Regeln äußerst sorgfältig formuliert.)

Turbulenz

Zwei der Millionen-Probleme betreffen sogar Phänomene der Natur, genauer gesagt: das mathematische Verständnis dieser Phänomene. Es geht einerseits darum, dass Wasser und Luft gelegentlich von der glatten zur turbulenten Srömung übergehen, andererseits darum, dass Materie Masse hat, dass es also nicht nur Kräfte gibt, sondern auch etwas, das diese Kräfte beschleunigen.

Die Physiker fassen Flüssigkeiten und Gase unter dem Oberbegriff "Fluide" zusammen, denn für beider Bewegung gilt, abgesehen von unterschiedlichen Zahlenwerten, dieselbe Gleichung: die Navier-Stokes-Gleichung, die eigentlich aus zwei Gleichungen besteht. Sie beschreibt, wie die physikalischen Gesetze (im Wesentlichen Newtons berühmte Formel "Kraft ist Masse mal Beschleunigung") den Zustand einer Strömung an einem bestimmten Ort und zu einer bestimmten Zeit verändern.

Man interessiert sich für die Lösung des Anfangswertproblems zur Navier-Stokes-Gleichung: Gegeben ist der Zustand des Fluids zu einem gewissen Anfangszeitpunkt, gesucht ist sein Verhalten in der Zukunft. Im Allgemeinen ist diese Lösung extrem schwer zu finden. Exakte Lösungen gibt es nur in sehr wenigen, uninteressanten Fällen: Wenn der See zum Anfangszeitpunkt in völliger Ruhe ist und keine äußeren Kräfte wirken, wird er für alle Zeiten ruhen. Wer etwas bewegtere Verhältnisse beherrschen will, weil er beispielsweise ein Flugzeug baut, behilft sich meist recht erfolgreich mit numerischen Näherungslösungen. Aber man möchte natürlich trotzdem wissen, ob exakte Lösungen überhaupt existieren, einerlei wie die Anfangsbedingungen aussehen.

Und hier liegt das Problem: Es ist nichtbekannt, ob die Navier-Stokes-Gleichung immer eine Lösung hat. Im Prinzip könnte ein Fluid eine "Singularität" entwickeln – einen oder mehrere Punkte, in denen die Strömung nicht mehr stetig ist, sodass die Gleichung ihren Sinn verliert. Zum Beispiel könnte das Fluid um einen solchen Punkt im Kreise herumströmen, und zwar um so schneller, je genauer man hinschaut, das heißt je näher das Fluid dem zentralen Punkt ist. Die Millennium-Aufgabe ist es, zu beweisen, dass genau das nicht passieren kann: Wenn die Anfangsbedingungen glatt (differenzierbar) sind, dann bleibt die Strömung für alle Zeit glatt.

Oder genau das zu widerlegen! Wer ein System glatter Anfangsbedingungen findet, für das die Strömung nicht glatt bleibt, hat den Preis auch gewonnen. Das analoge Problem in zwei Dimensionen wurde in den 1960er Jahren gelöst: Olga Ladyzhenskaya vom Steklov-Institut in St. Petersburg (damals Leningrad) zeigte, dass glatte Anfangsbedingungen stets glatte Strömungen hervorbringen. Für den dreidimensionalen Fall ist immerhin ein Teilresultat bekannt: Alle anfangs glatten Strömungen bleiben zumindest für einen kleinen Zeitraum glatt, und eine hinreichend langsame glatte Strömung bleibt für immer glatt.

Was die Sache in drei Dimensionen so schwierig macht, sind Turbulenzen (die es in zwei Dimensionen einfach nicht gibt). Um eine turbulente Strömung zu verfolgen, muss man sie immer genauer beobachten: Kleine Wirbel erzeugen noch kleinere Wirbel, und diese noch kleinere, und so weiter. Sehr grob gesagt läuft die große Frage nach der Existenz und Glattheit der Lösungen darauf hinaus, wie schnell dieser Übergang von kleinen zu noch kleineren Größenskalen stattfindet. Wenn man etwa einmal pro Sekunde die Vergrößerung verdoppeln muss, um mitzuhalten, dann wird die Strömung gleichwohl immer glatt bleiben – nach n Sekunden muss man eben 2ⁿ-mal so genau hinschauen. Wenn man aber nach einer Sekunde die Vergrößerung verdoppeln muss, nach einer halben Sekunde schon wieder, das nächste Mal nach einer Viertelsekunde und so weiter, dann ist es nach zwei Sekunden vorbei mit der Stetigkeit.

Warum gibt es keine beliebig kleinen Quarks?

Während die Navier-Stokes-Gleichung die klassische Mechanik betrifft, kommt das andere physikalische Problem auf der CMI-Bestenliste aus der Quantentheorie. Es geht darum zu zeigen, dass das Grundgerüst, das in der mathematischen Physik üblicherweise für das Studium von Quantenfeldern verwendet wird, die so genannte Yang-Mills-Theorie, wirklich die subatomare Welt aus Quarks, Gluonen und dem Rest des Teilchenzoos beschreibt. Insbesondere sollte die Theorie "Massenlücken" im Energiespektrum vorhersagen können. Die Energie des leeren Raums ist gleich null, aber sobald auch nur ein Teilchen auftaucht, ist sie mindestens gleich einer gewissen Minimalenergie E. Nach Einsteins Formel E=mc² kann man dem Teilchen die Masse m zuordnen. Zu beweisen ist also, dass nach der Yang-Mills-Theorie Energien zwischen 0 und E nicht vorkommen können.

Aus der aktuellen Version der Yang-Mills-Theorie, der Quantenchromodynamik (QCD), folgt mit großer Wahrscheinlichkeit eine solche Massenlücke, zusammen mit anderen wünschenswerten Eigenschaften wie der asymptotischen Freiheit und den Einschluss (confinement) von Quarks. (Erstere bedeutet, dass bei immer kürzeren Abständen das Quantenverhalten des Feldes immer besser durch die klassische Theorie approximiert wird; letztere erklärt, warum Quarks praktisch nie alleine, sondern stets nur zu zweit oder zu dritt vorkommen.) Das lassen zumindest Computerberechnungen zur QCD vermuten, und ihre Voraussagen wurden bis jetzt durch Experimente bestätigt. Aber ein strenger Beweis fehlt.

Die offizielle Formulierung des Problems geht über die Chromodynamik hinaus. QCD ist nur eine von vielen Yang-Mills-Theorien, und zwar diejenige, die auf einer so genannten Eichgruppe von Symmetrien namens SU(3) beruht. (Grob gesprochen ist SU(3) die Gruppe der Rotationen im dreidimensionalen komplexen Raum.) Gefordert ist zu zeigen, dass eine (noch zu entwickelnde) Yang-Mills-Theorie für alle Eichgruppen eine Massenlücke aufweist. Das ist wirklich viel verlangt, aber theoretische Physiker halten dies für unbedingt erforderlich, um Quantenfelder zu verstehen.

Von schweren und ganz schweren Rechenaufgaben

Das letzte Millennium-Problem ist unter dem Namen "P=NP" bekannt und führt in das Herz der Informatik. Es geht darum, ob Aufgaben, die heute jeden Computer überfordern, das in alle Zukunft tun werden werden. Gibt es Rechenprobleme, die Computer niemalswerden bewältigen können?

Sowohl P als auch NP sind Klassen von Problemen, genauer gesagt, "Entscheidungsproblemen", die eine einfache Ja-Nein-Antwort verlangen. Zum Beispiel: Hat die Zahl 1002011 irgendeinen Teiler kleiner als 1000? Viele Optimierungsprobleme, etwa das Finden einer kürzesten Route beim Problem des Handlungsreisenden, lassen sich auf einen Satz von solchen Ja-Nein-Fragen reduzieren.

Bei Problemen der Klasse P wächst die Arbeit, die man zur Lösung aufwenden muss, nicht schneller als polynomial in der "Größe" des Problems. Um etwa zu entscheiden, ob zwei N-stellige Zahlen einen gemeinsamen Teiler haben, sind – mit dem euklidischen Algorithmus – größenordnungsmäßig N² Rechenschritte auszuführen. Solche Probleme sind relativ einfach, weil die zusätzliche Zeit, die für die Lösung eines etwas größeren Problems benötigt wird, nur ein Bruchteil der Zeit ist, die schon für die kleinere Version verwendet wurde. Wenn ein Computer zum Beispiel eine Sekunde braucht, um den größten gemeinsamen Teiler zweier 1000-stelliger Zahlen zu finden, dann sollte er für zwei 1001-stellige Zahlen nur zwei Millisekunden mehr benötigen.

Die Klasse NP – die Abkürzung bedeutet "nicht-deterministisch polynomial" – ist schwieriger zu beschreiben. Grob gesagt besteht NP aus Problemen, für die vorgeschlagene Lösungen einfach nachzuprüfensind. Die Faktorisierung ist ein gutes Beispiel: Die Antwort auf die Frage nach den Teilern von 1002011 ist "ja", wie man leicht mit einem Taschenrechner nachprüfen kann, indem man durch 733 dividiert. "Einfach" meint hier, dass die vorgeschlagene Lösung mit einer Berechnung nachgeprüft werden kann, die polynomial mit der Größe des Problems anwächst. Aber die vorgeschlagene Lösung kann von überall her kommen: aus einer erschöpfenden Suche, durch einen Zufallstreffer oder irgendeine Art von Insider-Wissen. Das ist es, was die Sache nicht-deterministisch macht.

Genauer ausgedrückt, besteht NP aus jenen Ja-Nein-Problemen, die einfach nachzuprüfen sind, falls die Antwort "ja" ist. Das Gegenstück von NP (für die Antwort "nein") heißt co-NP. Die Frage, ob eine bestimmte Zahl eine Primzahl ist, gehört zum Beispiel zu co-NP, weil es einfach ist, einen Teiler als solchen nachzuweisen, wenn man zufällig einen weiß. (Obendrein gehört das Problem ebenso wie das Faktorisierungsproblem in beideKlassen, NP und co-NP. Das ist allerdings nicht unmittelbar einzusehen. Zahlentheoretiker haben eine Theorie der "Primzahl-Zertifikate" entwickelt, mit der man mit einem polynomialen Rechenaufwand nachweisen kann, dass eine große Zahl prim ist.)

P ist eine Teilmenge sowohl von NP als auch co-NP. Alle drei Klassen gehören zu einer größeren Klasse, die PSPACE genannt wird, und die wiederum zu einer noch größeren Klasse von Problemen namens EXP gehört. EXP besteht aus Ja-Nein-Problemen, die man mit einem exponentiellen Aufwand an Zeit und Speicherplatz lösen kann, möglicherweise weil sie Zwischenergebnisse verlangen, die exponentiell viele Stellen haben. Beispiel: Enthält die Dezimaldarstellung von 2²^ⁿ eine gerade Zahl von Einsen? PSPACE-Probleme verlangen eine weniger aufwendige Buchhaltung. Sie erfordern zwar einen exponentiellen Aufwand an Zeit, kommen aber mit einer – abwischbaren – Tafel von polynomialer Größe aus.

Die Informatiker glauben, dass P echtkleiner als NP ist, dass NP echt kleiner als PSPACE und PSPACE echt kleiner als EXP ist. Sicher ist bisher nur, dass P echt kleiner als EXP ist: Es gibt tatsächlich Probleme, die in polynomialer Zeit nicht gelöst werden können. Aber es könnte dennoch sein, dass P=NP=PSPACE, NP=PSPACE=EXP sowie jede andere Kombination, aus der nicht P=EXP folgt, richtig ist.

Das Millennium-Problem beschränkt sich auf P und NP, weil diese die meisten Probleme enthalten, für deren Lösung in der Praxis Computer verwendet werden. Kurz gesagt: P sind die Probleme, die man lösen kann, NP sind diejenigen, die man lösen will.

Hin und wieder wird für ein Problem, das man der Klasse NP zugerechnet hatte, gezeigt, dass es in P liegt. Dem Problem der linearen Optimierung wurde eine solche Zurückstufung zuteil, als 1979 Leonid Khachian einen polynomialen Algorithmus fand. (Khachians Methode wurde 1984 von Narendra Karmarkar von den Bell Labs deutlich verbessert.) Aber über einige NP-Probleme weiß man mehr. Sie gehören nur dann zu P, wenn alle NP-Probleme zu P gehören. Diese Probleme werden NP-vollständig genannt. Das Konzept wurde 1971 von Stephen Cook von der Universität Toronto eingeführt, der auch das erste Beispiel für ein NP-vollständiges Problem gab. Heute weiß man von Tausenden Problemen, dass sie NP-vollständig sind. Im Wesentlichen enthält jedes einzelne von ihnen alle Schwierigkeiten, die für die Klasse NP charakteristisch sind. Wenn Sie also, um P≠NP zu beweisen, ein Problem in NP suchen, das in polynomialer Zeit nicht gelöst werden kann, dann macht es Sinn, sich auf die NP-vollständigen zu konzentrieren.

Alternativ dazu könnten Sie einen polynomialen Algorithmus für ein NP-vollständiges Problem finden. Wenn Ihnen dies gelingt, dann haben Sie einen polynomialen Algorithmus für alleProbleme in NP gefunden, und die Clay-Stiftung wird Sie zum Millionär machen. Aber diese Million wird verblassen hinter dem, was Sie erreichen können, wenn Sie all die kryptographischen Systeme knacken, deren Sichrheit darauf beruht, dass NP-Probleme schwer sind.

Das CMI hat sich zum Ziel gesetzt, "die Schönheit, Kraft und Universalität des mathematischen Denkens zu fördern". Es hofft darauf, dass die ausgelobten Preise nicht nur zu neuen Versuchen führen, diese sieben wichtigen Probleme zu lösen, sondern auch mehr junge Leute zur Mathematik locken werden. Der intellektuelle Gewinn ist beträchtlich. Und die Bezahlung ist auch nicht schlecht.

Übrigens könnte die erste Million demnächst fällig werden. Grigori (Grisha) Perelman vom Steklov-Institut in St. Petersburg hat Ende 2002 eine erste Zusammenfassung und im Frühjahr einen ausführlicheren Beweis für die Poincarésche Vermutung vorgelegt. Noch brüten die Experten über den Einzelheiten der Argumentation; aber die Zuversicht ist ungefähr so groß wie vor zehn Jahren, als Andrew Wiles seinen Beweis der Fermatschen Vermutung vortrug.

Die elliptische Kurve y^2 + y = x^3 – x besteht aus zwei Teilen. Will man die Summe zweier Punkte der Kurve berechnen, so verbindet man diese Punkte durch eine Gerade. Diese schneidet die elliptische Kurve in einem dritten Punkt; der ist bis aufs Vorzeichen gleich der gesuchten Summe. Für Summen der Form P + P = 2P und den Punkt 0, der "im Unendlichen" liegt, gelten Sonderregeln.

Elliptische Kurven

Den Zahlentheoretiker interessiert an einer elliptischen Kurve weniger die wohlgeformte Krümmung, sondern eigentlich nur die Menge der Zahlenpaare (x,y), welche die zugehörige algebraische Gleichung erfüllen. Über eine bestimmte Formel lässt sich nämlich zu je zwei solcher Zahlenpaare (Punkte) ein drittes bestimmen, das man dann deren Summe nennt, denn die so definierte Verknüpfung erfüllt die klassischen Rechenregeln für die Addition. Sie ist sogar geometrisch motiviert (Bild); aber das spielt im Folgenden nur eine Nebenrolle. Die Menge aller Punkte einer elliptischen Kurve ist damit eine Gruppe im Sinne der Algebra.

Die Summe zweier rationaler Punkte auf einer elliptischen Kurve ist wieder ein rationaler Punkt. Daher bilden die rationalen Punkte eine Untergruppe der oben genannten Gruppe; auf beide Gruppen kann man die zahlreichen Analysewerkzeuge der Gruppentheorie anwenden, mit denen man insbesondere Gruppen in kleinere Bestandteile zerlegen kann.

Die Untergruppe der rationalen Punkte ist zerlegbar in eine endliche Gruppe T plus r Exemplare einer wohlbekannten Gruppe namens Z: der Gruppe der ganzen Zahlen. Die ganze Zahl r wird der "Rang" der Kurve genannt. Dies ist für sich selbst ein tiefgründiger mathematischer Satz, der 1901 von Henri Poincaré vermutet und 1922 von L. J. Mordell bewiesen wurde.

Die Vermutung von Birch und Swinnerton-Dyer sagt aus, dass E genau dann Rang r hat, wenn L_E an der Stelle 1 eine r-fache Nullstelle hat, das heißt wenn L_E(s)/(s-1)^r für s gegen 1 gegen einen Grenzwert ungleich 0 strebt. Birch und Swinnerton-Dyer brachten darüber hinaus den Wert dieses Grenzwertes mit verschiedenen Eigenschaften der elliptischen Kurve in Verbindung, aber das zu beweisen ist nicht mehr Bestandteil des Millennium-Problems.

In den vergangenen 25 Jahren wurde mancher Fortschritt erzielt. So bewiesen 1977 John Coates und Andrew Wiles von der Universität Cambridge einen Spezialfall der Vermutung: Für elliptische Kurven mit so genannter komplexer Multiplikation ist der Rang der Kurve 0 genau dann, wenn L_E(s) bei s=1 einen Grenzwert ungleich 0 hat; das ist die Aussage der Vermutung für r=0. 1983 zeigten Benedict Gross von der Brown University und Don Zagier von der Universität von Maryland, dass der Rang jeder "modularen" elliptischen Kurve – das heißt einer elliptischen Kurve mit einer dazugehörigen Modulform – mindestens 1 ist, wenn L_E(s)/(s-1) bei s=1 einen Grenzwert ungleich 0 hat. 1990 konnte Victor Kolyvagin vom Moskauer Steklov-Institut beide Resultate verschärfen. Er zeigte, dass der Satz von Coates und Wiles nicht nur für elliptische Kurven mit komplexer Multiplikation gilt, sondern für die größere Klasse der modularen elliptischen Kurven, und dass der Rang im Satz von Gross und Zagier nicht nur mindestens gleich 1, sondern genau gleich 1 ist.

Inzwischen weiß man, dass alle elliptischen Kurven modular sind. Das ist der Inhalt der Vermutung von Taniyama und Shimura; auf einen Spezialfall dieser Vermutung baute der oben genannte Andrew Wiles 1994 seinen Beweis der Fermatschen Vermutung auf, der ihn weltberühmt machte (Spektrum der Wissenschaft 1/1998, S. 96). Dadurch gilt Kolyvagins Resultat ganz allgemein. Aber es beweist noch nicht die Vermutung von Birch und Swinnerton-Dyer, weil es über den Zusammenhang zwischen dem Grenzwert von L_E(s)/(s-1)^r bei s=1 und dem Rang r für r > 1 keine Aussage macht. Vielleicht liegt in einer unbeobachteten Ecke der Zahlentheorie eine elliptische Kurve, für die L_E(s)/(s-1)² bei s=1 ungleich 0 ist, die aber einen von 2 verschiedenen Rang hat – vielleicht sogar 1 oder 0.

Was ist eine 3-Sphäre?

Man nähert sich der Frage am besten über die niedrigeren Dimensionen. Die 1-Sphäre ist einfach der gewöhnliche Kreis. Die Theorie der kompakten eindimensionalen Mannigfaltigkeiten ist extrem einfach: Die 1-Sphäre ist die einzige. Die Fundamentalgruppe der 1-Sphäre ist übrigens nicht trivial: Der Kreis selbst ist eine Schlaufe, und es gibt keine Möglichkeit, sie zu einem Punkt zusammenzuziehen.

Die 2-Sphäre ist die Oberfläche einer gewöhnlichen Kugel. Wie der Kreis kann auch sie algebraisch definiert werden, und zwar mit der Gleichung x²+y²+z²=1. Topologen nennen dies eine "Einbettung" der 2-Sphäre in den R³. Eine schöne Eigenschaft der zweidimensionalen Mannigfaltigkeiten ist, dass jede (orientierbare) zweidimensionale Mannigfaltigkeit in den R³ eingebettet werden kann.

Die 3-Sphäre lässt sich am einfachsten algebraisch definieren. Sie ist die Lösungsmenge der Gleichung x²+y²+z²+w²=1 im R⁴. Leider kann man sich Objekte im vierdimensionalen Raum nur schwer vorstellen. Aber es gibt eine gute Krücke; wir erläutern sie wieder mit der 1- und der 2-Sphäre.

Den Kreis fassen wir auf als die ganze Zahlengerade plus einen zusätzlichen Punkt, der den Bogen schließt. Diese Übereinstimmung erhalten wir über eine einfache Abbildung, die so genannte stereographische Projektion. In gleicher Weise ist die 2-Sphäre die vollständige unendliche Ebene mit einem zusätzlichen Punkt, dem "Nordpol". Denn der Nordpol der Sphäre, das heißt der Punkt, von dem die Projektion ausgeht, ist der einzige Punkt der Sphäre, der unter der Projektion kein Bild in der Ebene hat.

Die 1-Sphäre ist der Gerade sehr ähnlich und die 2-Sphäre der Ebene; nur werden beide durch den zusätzlichen "Punkt im Unendlichen" endlich gemacht, "kompaktifiziert". Entsprechend ist die 3-Sphäre weitgehend dasselbe wie der dreidimensionale euklidische Raum, bis auf den etwas mysteriösen, zusätzlichen Punkt im Unendlichen.

Aus: Spektrum der Wissenschaft 11 / 2003, Seite 1
© Spektrum der Wissenschaft Verlagsgesellschaft mbH