10 Claude agents spend 15 hours to beat Dijkstra on paper — then lose to it by up to 2.8x in practice
新智元 · wechat · 2026-09-27
- ValsAI ran 10 Claude Opus 5.5 agents in a sandbox for 15 hours (733 discussion entries); they produced C-HD, a shortest-path algorithm claimed to asymptotically beat Dijkstra in a sparse-graph regime, with 289 Lean proof files that passed kernel verification first try.
- The twist: developer danalec implemented C-HD in 1,900 lines of C and benchmarked it — it ran 1.4–2.8x slower than plain Dijkstra and 1.8–2.9x slower than 2025's DMMSY.
- The proofs weren't wrong; constant-factor explosion was: 59% of runtime on 16-byte label handling and 34% on preprocessing, so theoretical wins never recover the overhead at realistic graph sizes.
- Still a milestone for multi-agent collaboration plus formal verification: AI entering unexplored pure-theory territory, even if the result is practically useless.
More from Research
- FuseReg: Layer-Fusion Regularization Cuts gFID up to 29% in Representation Autoencoders — USC-PSI-Lab · 2026-09-28
- Kaggle Game Arena: Evaluating LLMs via Head-to-Head Chess, Poker, and Werewolf — kaggle · 2026-09-28
- InternW0-Δ: A World Action Model Trained on 20K+ Hours of Open Robot Data, Fully Open-Sourced — Xingyu Miao · 2026-09-28
- Berkeley's Morphometric Imitation Hits 89.3% Zero-Shot Real-World Success Across 3 Robot Hands — Berkeley · 2026-09-28
- Fermi estimate: brain may pack 500k-5M molecular switching units per 'parameter' — JosephJacks_ · 2026-09-28
- Contrastive World Models: swapping pixel reconstruction for InfoMax boosts robustness — burny_tech · 2026-09-28