Исследователь Vals AI поставил десяти агентам Claude Opus 5.5 задачу: придумать более быстрый алгоритм поиска кратчайших путей и доказать его свойства в Lean. Через 15 часов агенты представили алгоритм C‑HD. Он находит точные расстояния от одной вершины до остальных в ориентированном графе с неотрицательными весами.
Для этой задачи привычный ориентир: алгоритм Дейкстры с оценкой O(m + n·log n), где n — число вершин, а m — число рёбер. При m ≈ n·log^(3/4) n доказанная оценка C‑HD составляет O(n·log^(11/12) n). В этом диапазоне она асимптотически лучше оценки Дейкстры и опубликованных ранее алгоритмов.
Это первое доказанное улучшение именно в этой разреженной зоне, где лучшим все еще был Дейкстра. Если взять конкретный пример, то в сравнении с алгоритмом Дейкстры при n = 2^1000 выигрыш составляет ~1,78х и растет с размером графа.
Практическое ускорение пока не показано: автор проверял корректность на небольших примерах, но не измерял скорость на больших графах. Он также предупреждает об огромных константах в формальной конструкции; независимого рецензирования результата пока нет.
Если новость понравилась, приглашаю в канал AI for Devs. Каждый день публикую похожие материалы: новые модели, агенты, практические кейсы и новости из мира AI.
