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.