10 агентов Claude теоретически обошли алгоритм Дейкстры

В Vals AI запустили 10 агентов Claude Opus 5.5, которые за 15 часов и 733 сообщения разработали алгоритм C-HD для поиска кратчайших путей в ориентированных графах.

Для графов с определённой плотностью сложность снизилась с O(n log n) у Дейкстры до O(n log¹¹⁄¹² n). Корректность и оценка времени работы формально подтверждены доказательством в Lean.

Но это пока теоретический результат. Алгоритм не тестировали на крупных реальных графах, константы велики, а улучшение действует только в ограниченном диапазоне входных данных.

Главное здесь другое: группа ИИ-агентов смогла самостоятельно разработать алгоритм и подготовить его формальное доказательство всего за 15 часов.

https://www.vals.ai/blogs/faster-shortest-path-algorithm