10 Opus-5.5-Agenten entdecken kürzeste-Pfad-Algorithmus, der Dijkstra in 15 Stunden schlägt

Das Problem des kürzesten Pfads ist eine klassische Herausforderung der Graphentheorie und bildet die Grundlage für moderne Navigationssysteme, Internet-Routing, Logistik und unzählige andere reale Anwendungen. Im Jahr 1959 schlug der niederländische Informatiker Edsger Dijkstra einen Algorithmus mit einer Komplexität von O(m + n log n) vor, der über die nächsten 65 Jahre hinweg der Goldstandard blieb und allgegenwärtig eingesetzt wurde.

Im Jahr 2025 gelang es einem Team aus der Tsinghua-Universität, Stanford und dem Max-Planck-Institut, diese Schranke mit einer O(m log^{2/3} n)-Komplexität zu unterbieten. Der Vorteil dieser Lösung zeigt sich jedoch nur bei hinreichend dichten Graphen (wo die Anzahl der Kanten m ≥ die Anzahl der Knoten n ist). Bei dünn besetzten Graphen (sparse graphs) blieb der Dijkstra-Algorithmus weiterhin überlegen.

Vals AI beschloss, das neue Modell Opus 5.5 gezielt auf diesem ungelösten Bereich zu testen (Blogbeitrag). Das Unternehmen startete 10 Agenten, wies ihnen die Aufgabe zu und stellte ein "Bulletin Board" zur Verfügung, auf dem sie Ideen austauschen und kooperieren konnten.

Innerhalb von nur 15 Stunden und nach 733 Nachrichten leiteten die Agenten den C-HD-Algorithmus ab und verifizierten ihn formal. Dies ist der erste bewiesene Fortschritt speziell im Bereich dünn besetzter Graphen, in dem Dijkstra bisher das Maß aller Dinge war: Bei m ≈ n·log^{3/4}n erreicht C-HD eine Komplexität von O(n·log^{11/12}n), verglichen mit Dijkstras O(n log n). Für n = 2^1000 beträgt der Geschwindigkeitsgewinn etwa das 1,78-Fache und wächst mit der Größe des Graphen.

Trotz der beeindruckenden Behauptung und der Existenz eines Beweises in Lean gibt es noch keine Hinweise auf einen praktischen Geschwindigkeitsvorteil, da die oben genannten Schätzungen asymptotischer Natur sind. Der Algorithmus wurde noch nicht auf realen Graphen benchmarkt. Mit anderen Worten: Während garantiert ist, dass eine Kurve die andere überholt, wenn n gegen Unendlich strebt, könnte der Schnittpunkt in der Praxis erst bei enorm großen n-Werten liegen. Auf jedem realistischen Graphen wird Dijkstra wahrscheinlich immer noch schneller sein, trotz schlechterer Asymptotik. Dieser Aspekt muss noch validiert werden.