Spielman und Teng definierten 2001 die "geglättete Komplexität"

"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!"