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
- Google Research open-sources PaperOrchestra, a multi-agent framework for writing AI papers — google-research · 2026-11-16
- Kind ICLR Reviewer Raises Score Despite Unresolved Concerns, Citing the Paper's Value — MarkSchmidtUBC · 2026-11-16
- Hand-editing 0.2% of weights plus 100 CPU-minutes turns an English TTS model into an 18MB Sanskrit one — kastnerkyle · 2026-11-16
- Why chirality matters for AI for Science: enantiomers behave differently in biology — madeofAjala · 2026-11-16
- RSS 2027 submissions open with FAQ clarifying two-stage review and negative-result bar — GeorgiaChal · 2026-11-16
- Mobile AI Factory: agents auto-build on-device SLMs with 19x less GPU time — pmttyji · 2026-11-16