Als Nathan Klein 2018 zu promovieren begann, schlugen ihm seine Betreuer ein ambitioniertes Projekt vor: die Mitarbeit an einem der bekanntesten Probleme der theoretischen Informatik. Selbst wenn sie es nicht lösen sollten, würde der Student viel dabei lernen. Daher schloss er sich der Idee spontan an. »Mir war nicht ganz klar, welche Tragweite das hatte«, gibt er zu. »Ich war schließlich in meinem ersten Promotionsjahr – ich hatte keine Ahnung.«

Im Juli 2020 hat Klein schließlich gemeinsam mit seinen Betreuern Anna Karlin und Shayan Oveis Gharan von der University of Washington ein Ergebnis veröffentlicht, dem Computerwissenschaftler seit fast einem halben Jahrhundert nachjagen: Sie haben einen Algorithmus entwickelt, der bessere Lösungen für das so genannte Problem des Handlungsreisenden findet.

Ziel ist es hierbei, den kürzesten Rundweg zwischen einer vorge­gebenen Menge an Städten – oder allgemein Orten – zu bestimmen. Die Aufgabe hat Anwendungen, die von der DNA-Sequenzierung bis zur Logistik einer Mitfahrzentrale reichen. Im Lauf der Jahrzehnte hat das Problem zu etlichen grundlegenden Fortschritten in der Informatik geführt und dazu beigetragen, bekannte Techniken wie die lineare Programmierung zu beleuchten. Dennoch haben Wissenschaftler das gesamte Potenzial der Optimierungsaufgabe noch lang nicht ausgeschöpft – was nicht daran liegt, dass sie es nicht eingehend untersucht hätten.

Ob überhaupt ein Algorithmus existiert, der das Problem des Handlungsreisenden in annehmbarer Zeit exakt löst, ist unklar …