10 agentów Opus 5.5 odkryło algorytm krótszej drogi przewyższający Dijkstrę w 15 godzin

Problem najkrótszej ścieżki to klasyczne wyzwanie w teorii grafów, stanowiące fundament nowoczesnej nawigacji, routingu internetowego, logistyki oraz niezliczonych innych zastosowań w świecie rzeczywistym. W 1959 roku holenderski informatyk Edsger Dijkstra zaproponował algorytm o złożoności obliczeniowej O(m + n log n), który przez kolejne 65 lat pozostawał złotym standardem i był powszechnie stosowany.

W 2025 roku zespół z Tsinghua University, Stanfordu i Instytutu Maxa Plancka ostatecznie przebił ten wynik, uzyskując granicę O(m log^{2/3} n). Jednak przewaga ich rozwiązania ujawnia się jedynie na wystarczająco gęstych grafach (gdzie liczba krawędzi m ≥ liczbie wierzchołków n). Na grafach rzadkich algorytm Dijkstry nadal pozostawał lepszy.

Vals AI postanowiło przetestować nowy model Opus 5.5 właśnie w tym niepokonanym zakresie (post na blogu). Uruchomiono 10 agentów, przydzielono im zadanie i udostępniono „tablicę ogłoszeń” do wymiany pomysłów i współpracy.

W rezultacie, w ciągu 15 godzin i 733 wiadomości, agenci wyprowadzili algorytm C-HD i formalnie go zweryfikowali. Jest to pierwszy udowodniony postęp konkretnie w strefie rzadkiej, gdzie Dijkstra wciąż dominował: przy m ≈ n·log^{3/4}n, C-HD osiąga złożoność O(n·log^{11/12}n) w porównaniu z O(n log n) dla Dijkstry. Przy n = 2^1000 zysk wynosi około 1,78x i rośnie wraz z rozmiarem grafu.

Niemniej, mimo imponującego twierdzenia i istnienia dowodu w systemie Lean, nie ma jeszcze mowy o praktycznym przyspieszeniu, ponieważ powyższe szacunki są asymptotyczne. Algorytm nie został jeszcze poddany benchmarkingowi na rzeczywistych grafach. Innymi słowy, choć jedna krzywa jest gwarantowana do wyprzedzenia drugiej gdy n → ∞, punkt przecięcia w praktyce może wystąpić dopiero przy ogromnych wartościach n, a na każdym realistycznym grafie Dijkstra prawdopodobnie nadal będzie szybszy, mimo gorszej asymptotyki. Ta część pozostaje do weryfikacji.