10体のAIエージェントが15時間でDijkstraを超える最短経路アルゴリズムを発見
A Faster Shortest Path Algorithm
Vals AIが、10体のClaude Opus 5.5エージェントにメッセージボードを与え、15時間・733メッセージで非負実数重み付き有向グラフの厳密最短経路アルゴリズムC-HDを開発。DijkstraのO(m+n log n)に対し、特定の密度領域でO(n(log n)^{11/12})を達成し、Leanで証明を形式検証した。ただし定数が巨大で実用的な高速化は未確認。
OpenAIのHugging Face事件とNavier–Stokesの結果が教えてくれたのは、エージェントが問題の進展にかかる時間を劇的に圧縮できるということだ。
- swiftcoder
正しく読めているなら、これは理論上の改善のひとつで、実用的な高速化を大してテーブルに載せるものではない。ただ、今後数か月で計算機科学の他のどれだけのアルゴリズムがその限界を下げることになるのか、気になるところだ
- sashank_1509
ここで水を差すつもりはないが、これはAIスロップな数学やCSによくある話だ。複雑さの上に複雑さを積み上げて、逓減する改善を生み出すだけ（今回の場合、実用的な高速化にはつながらない）。これはコードでの自分の経験でもあり、限られた範囲で知っている数学での経験でもある。
AIがこの分野で人間より上手くなりつつある今、妥当な結論は、人間はこういうことをやめるべきだということだと思う。人間が過去にこういうことをやるべきではなかった強い理由があると思うが、今やそれははるかに明白で、AIはあなたが築けるどんな複雑さをも凌ぐ複雑さを生み出し、込み入った複雑さの扱いであなたを打ち負かすだろう。
人間は10倍の改善につながるシンプルな解を見つけることに集中すべきだ。AIがこれをやることはまれだが、数学で時々やっているのを目にしたことはある。ただしそれは、解がすでにどこか遠くの文献に存在していて、2つの遠く離れた領域の専門知識を持つ人間がいなかった場合だ。AIがこれをやるときは歓迎すべき進歩であり、それが示す橋渡しがエキサイティングな新展開につながることを願う。
しかしLLMがこれをやることはまれで、人間はもっぱらこれに集中すべきだと思う。なぜなら、物事をシンプルに保ち、10倍、100倍の改善につながる新しい洞察を見つけることにかけては、我々はLLMよりはるかに優れているように思えるからだ
- EdSchouten
この記事で示されている時間計算量は、mとnではなく|V|と|E|を使っていればもっと読みやすかっただろう。