A team of ten Claude Opus 5.5 AI agents, working autonomously for roughly 15 hours across 733 message-board exchanges, produced C-HD—a formally verified shortest-path algorithm that improves on the published asymptotic upper bounds in a specific density regime. The result targets exact single-source shortest paths on directed graphs with non-negative real edge weights, where n is the number of vertices and m the number of edges. In that setting, Dijkstra’s algorithm runs in O(m + n log n), while recent breakthrough papers achieve bounds such as O(m log^(2/3) n) and O(m√log n + √(mn log n log log n)). C-HD carves out a region of the parameter space where it beats both Dijkstra and these state-of-the-art algorithms, and the entire correctness and efficiency claim is machine-checked in Lean.
The certified runtime bound is O(n + m + m log(2 + m/(n+1)) + m^(1/3)(n log(n+2))^(2/3)), valid within the certified range m ≤ n⌊⌊log₂ n⌋^(3/4)⌋. Along the density profile m ≈ n log^(3/4) n, this simplifies to O(n log^(11/12) n), compared with O(n log n) for Dijkstra. The improvement is polylogarithmic rather than dramatic: for n = 2^1000, the ratio of leading terms is about 1000^(1/12) ≈ 1.78, and squaring n only multiplies that ratio by 2^(1/12). The agents also included a Bellman–Ford fallback with O((n+1)(m+1)) runtime for small inputs and densities outside the certified range. Importantly, the paper is explicit that these are asymptotic upper bounds—not measured speedups—and that the constants in the formal construction are enormous, so no practical performance claim is made.
The algorithmic idea behind C-HD is to reduce repeated search and data-structure work. It starts from the source and current frontier, runs bounded local searches along outgoing edges, and counts newly encountered vertices—including unexplored leaves when an edge fails to improve a distance estimate—toward the search size limit. It uses the resulting search trees and pivots to organize recursive work, maintaining local invariants through careful edge deletion so that repeated processing of the same vertex or endpoint remains bounded. Sorted outgoing-edge lists are built as charged preprocessing, and the analysis accounts for memory allocation, sorting, input reading, and output.
The project is as notable for its methodology as for its mathematics. Ten agents were given maximum effort, distinct initial roles, and a shared message board allowing them to reorganize, share discoveries, challenge claims, and redirect effort. They were asked to compare against recent papers, log failed approaches, and require a reproducible Lean build plus two independent peer reviews before declaring success. A Lean Comparator tool verified that the submitted proof establishes the stated theorem, uses only permitted axioms, and is accepted by Lean’s kernel. The result illustrates how coordinated AI agents can compress research timelines, though the work’s own caveats—no large-scale benchmarks and no claim about other density regimes, such as m = 10n—keep the contribution firmly in the realm of theory. The full proof package, including Lean sources, an informal paper, and verification records, is available at github.com/spicylemonade/c-hd-proof.
Ez a cikk a Neural News AI (V1) verziójával készült.
Forrás: https://www.vals.ai/blogs/faster-shortest-path-algorithm.