Mathematik Rechnen mit Boxhandschuhen

Der Informatiker Daniel Spielman erhält den Rolf-Nevanlinna-Preis, weil er einen Algorithmus so glättete, dass er universal einsetzbar ist. Christoph Drösser hat den Preisträger auf der Mathematikerkonferenz in Hyderabad getroffen.

Am schlimmsten war es für Dan Spielman , seinem engsten Kollegen Shang-Hua Teng nichts erzählen zu dürfen. Die Träger der Preise , die auf der Internationalen Mathematiker-Konferenz (ICM) verliehen werden, bekommen den beglückenden Anruf einige Monate im Voraus, damit sie auch rechtzeitig ihre Reise organisieren können.

Allerdings wird ihnen ein strenges Schweigegelübde abverlangt: Ihrer Frau dürfen sie es erzählen (weibliche Preisträger gab es bisher nicht), aber nicht ihren Kollegen. Der Kollege Teng hätte die Nachricht wohl ohnehin mit gemischten Gefühlen aufgenommen: Die meisten wissenschaftlichen Arbeiten haben er und Spielman zusammen veröffentlicht, aber Teng geht leer aus. Er ist 46 Jahre alt, und für den Nevanlinna-Preis gilt ebenso wie für die Fields-Medaillen eine strikte Altersgrenze von 40 Jahren.

Dan Spielman lehrt am Informatik-Fachbereich der Yale-Universität in den USA, vorher war er Mathematiker am MIT in Cambridge . Theoretische Informatik und Mathematik – da sind die Grenzen fließend. Die Vorstellung, Informatiker würden vor allem Computer programmieren, ist nämlich falsch. Zumindest die Theoretiker bewegen sich in äußerst abstrakten Sphären, sie rechnen nicht, sondern machen sich Gedanken darüber, ob Dinge in vertretbarer Zeit berechenbar sind.

Dan Spielman und sein Kollege Teng haben sich vor allem mit dem linearen Programmieren beschäftigt. Ein typisches Beispiel: In den USA stehen auf Lebensmittelpackungen nicht nur die Inhaltsstoffe, sondern auch, welchen Prozentsatz des durchschnittlichen Tagesbedarfs an dem jeweiligen Stoff das Produkt abdeckt. Die lineare Programmieraufgabe lautet nun: Gehen Sie in den Supermarkt und kaufen Sie so ein, dass Sie exakt Ihren Tagesbedarf an allen lebenswichtigen Stoffen abdecken – und das zu einem möglichst günstigen Preis!

Auch wenn das kompliziert klingt, haben die Mathematiker dieses Problem schon 1947 gelöst, zumindest im Prinzip. Sie entwickelten einen Algorithmus, mit dem sich die Aufgabe lösen lässt – den Simplex-Algorithmus. Durch die Bedingungen der Aufgabenstellung wird ein Polytop definiert, ein Körper in einem hochdimensionalen Raum analog zu einem Polyeder in drei Dimensionen, und die optimale Lösung liegt immer auf einer Ecke dieses Polytops. Der Simplex-Algorithmus krabbelt auf geschickte Weise auf dem Polytop von Ecke zu Ecke und findet so die Lösung.

Seit Jahrzehnten wird der Algorithmus in der Praxis eingesetzt, aber seltsamerweise kann man Spezialfälle konstruieren, in denen er nicht funktioniert, das heißt: in denen der Rechenaufwand exponenziell steigt. Das sind stets sehr exotische, geradezu bösartig konstruierte Fälle. Aber Informatiker möchten immer gern beweisen, dass ein Algorithmus sich auch im schlimmsten Fall gutartig verhält oder zumindest in "durchschnittlichen" Fällen. Beides tut der Simplex-Algorithmus nicht.

"Diese Sonderfälle sind sehr schwer zu konstruieren", sagt Spielman. "Mein Koautor hat es mal so formuliert: Wenn man Boxhandschuhe trägt, dann kann man sie nicht produzieren." Es bedarf also einer gewissen filigranen Bosheit.

Die beiden nahmen sich vor, dieses Bild von den Boxhandschuhen in exakte mathematische Begriffe zu fassen. Sie fanden heraus, dass die "bösartigen" Probleme so speziell waren, dass man ihre Parameter nur ein bisschen abändern musste, um ein "gutartiges" Problem zu bekommen, das sich gut berechnen ließ. Und da in der Praxis sowieso nie ganz exakt gerechnet wird, sicherte das zumindest die angenäherte Lösbarkeit jedes linearen Problems mit Hilfe des Simplex-Algorithmus.

Spielman und Teng definierten 2001 die "geglättete Komplexität" von Algorithmen, und die beschreibt das Verhalten im schlimmsten Fall, wenn man ein wenig an den Eingabewerten wackelt. Das Konzept wurde in der Folge auf viele Algorithmen angewandt, weil es ihr Verhalten in der Praxis besser beschreibt, als wenn man ganz exakt die schlimmsten Fälle untersucht.

Das alles sind theoretische Resultate – die ersten praktischen Anwendungen der geglätteten Komplexität für neue Computerverfahren entstehen gerade erst, erzählt Spielman. Und es gibt durchaus Fälle, in denen er das Auf- und Abrunden der Eingabedaten nicht für angemessen hält: "Wenn ein Algorithmus über die Steuerung eines Flugzeugs entscheidet, dann sollte er besser auch im schlimmsten aller Fälle funktionieren!"