IN DER INFORMATIK FÄLLT EINE HÜRDE VON 1962

Ein Hamiltonkreis ist eine Rundreise durch ein Netz, die jeden Punkt genau einmal besucht und zum Start zurückkehrt. In einem gerichteten Netz ist jede Verbindung ein Pfeil, dem man nur in einer Richtung folgen kann, wie einer Einbahnstraße. Die gewichtete Version dieses Problems ist das asymmetrische Problem des Handlungsreisenden.

Zu entscheiden, ob ein solcher Kreis existiert, ist ein Lehrbuchbeispiel für ein schweres Problem. 1962 gaben Richard Bellman und unabhängig davon Michael Held und Richard Karp Algorithmen der dynamischen Programmierung an, die es für ein Netz aus n Punkten in einer Zeit von etwa 2ⁿ lösen (bis auf Faktoren, die nur polynomiell wachsen). Mehr als sechzig Jahre lang gelang es niemandem, bei allgemeinen gerichteten Netzen grundlegend besser zu werden.

Der ungerichtete Verwandte war schon gefallen

Für Netze mit Verbindungen in beide Richtungen durchbrach Andreas Björklund die Schranke 2014 mit einem randomisierten Algorithmus, der in 1,657ⁿ läuft — eine Arbeit, die ihm laut dem Paper den EATCS–IPEC-Nerode-Preis 2016 einbrachte. Er ist bis heute der schnellste bekannte für allgemeine ungerichtete Netze. Bei gerichteten Netzen gab es Fortschritte nur in Spezialfällen — bipartite Netze, Netze mit wenigen Verbindungen pro Punkt — oder unter einer unbewiesenen Annahme, Strassens Vermutung zum asymptotischen Rang.

Die neue Schranke

Tomohiro Koana von der Universität Tokio und Soh Kumabe von der Tokioter Firma CyberAgent legen nun einen randomisierten Algorithmus vor, der das gerichtete Problem in der Zeit

O((375/196)ⁿ) = O(1,9133ⁿ)**

entscheidet. Für allgemeine gerichtete Netze ist das die erste Verbesserung der Basis der Exponentialfunktion seit 1962.

Zählen nach gerade und ungerade

Die Schwierigkeit ist subtil. Kreise modulo 2 zu zählen — also nur zu wissen, ob ihre Anzahl gerade oder ungerade ist —, war bereits unterhalb von 2ⁿ möglich. Doch eine gerade Anzahl ungleich null sieht genauso aus wie null. Der klassische Ausweg: den Verbindungen zufällige Gewichte geben, sodass bei irgendeinem Gesamtgewicht eine Lösung eindeutig wird (das Isolationslemma); doch die schnelle Paritätszählmethode konnte mit Gewichten nicht umgehen.

Das Rezept der Autoren, in einfachen Worten:

1. Einen Pfeil des Kreises raten und stattdessen einen Weg durch alle Punkte suchen, vom einen Ende dieses Pfeils zum anderen.
2. Jeden Pfeil zufällig mit Wahrscheinlichkeit 1/50 löschen.
3. An jedem Punkt drei Gruppen eingehender Pfeile bilden und jeden verbliebenen Pfeil in eine zufällige, nicht leere Menge von Gruppen kopieren.
4. Existiert eine Rundtour, kann man mit Wahrscheinlichkeit mindestens (49/50)ⁿ⁻¹ pro Punkt eine Gruppe so wählen, dass die Zahl gültiger Wege ungerade ist.
5. Jeder Gruppe — nicht jedem Pfeil — ein zufälliges Gewicht geben. Jetzt funktioniert der Isolationstrick, und etwa (50/49)ⁿ Wiederholungen genügen.
6. Jede Wiederholung berechnet die Gerade-oder-ungerade-Zahlen für jedes Gesamtgewicht in der Zeit (15/8)ⁿ, mithilfe von Summen von Matrixdeterminanten nach Björklund, Kaski und Koutis und einer zufälligen „Linearisierung“, die auch Arvind und Guruswami verwendet haben.

Beides multipliziert: (50/49)ⁿ × (15/8)ⁿ = (375/196)ⁿ ≈ 1,9133ⁿ.

Ein von einer Maschine erzeugter Beweis

Das Paper endet mit einer Erklärung zu generativer KI: ChatGPT 6 Astra erzeugte den Beweis des Hauptsatzes und half beim Entwurf des Manuskripts. Die Autoren lieferten die Formulierungen der Zwischenaussagen, die eine kombinatorische Lesart der ursprünglichen Lösung des Modells bieten, prüften und überarbeiteten dann alles und übernehmen die volle Verantwortung.

Das Ergebnis ist theoretisch — es wurde kein Programm ausgeführt —, und der Algorithmus ist randomisiert, mit einer kleinen Fehlerwahrscheinlichkeit in beide Richtungen. Zwischen 1,9133 für Einbahnstraßen und 1,657 für Straßen in beide Richtungen klafft weiterhin eine große Lücke.