1962年以来の計算機科学の壁が崩れる

ハミルトン閉路とは、ネットワークのすべての地点をちょうど一度ずつ訪れて出発点に戻る周回路のことだ。有向ネットワークでは、各リンクは一方通行の道のように一方向にしかたどれない矢印である。この問題に重みをつけた版が、非対称巡回セールスマン問題だ。

そうした閉路が存在するかどうかを判定するのは、教科書に載っている難問である。1962年、リチャード・ベルマン(Richard Bellman)と、それとは独立にマイケル・ヘルド(Michael Held)とリチャード・カープ(Richard Karp)が、n個の地点からなるネットワークに対しておよそ2ⁿの時間(多項式的にしか増えない因子を除く)でこれを解く動的計画法のアルゴリズムを示した。それから60年以上、一般の有向ネットワークについて、本質的にこれより良い方法を見つけた者はいなかった。

無向の「いとこ」はすでに陥落していた

リンクが双方向のネットワークについては、アンドレアス・ビョルクルンド(Andreas Björklund)が2014年に1.657ⁿで動く乱択アルゴリズムでこの壁を破った。論文によれば、この業績で彼は2016年のEATCS–IPECネロード賞を受賞している。これは一般の無向ネットワークで知られている最速の方法として今も残っている。有向ネットワークについては、二部グラフや各地点のリンクが少ないネットワークといった特殊な場合か、未証明の仮説であるシュトラッセンの漸近ランク予想のもとでしか進展がなかった。

新たな上限

東京大学のコアナ・トモヒロ(Tomohiro Koana)と、東京の企業サイバーエージェントのクマベ・ソウ(Soh Kumabe)は、有向版の問題を

O((375/196)ⁿ) = O(1.9133ⁿ)**

の時間で判定する乱択アルゴリズムを示した。

一般の有向ネットワークにおいて、1962年以来初めて指数の底を改善した成果である。

奇数と偶数で数える

難しさは微妙なところにある。閉路の数を2を法として数えること、つまりその数が奇数か偶数かだけを知ることは、すでに2ⁿ未満で可能だった。しかし、ゼロでない偶数個の閉路は、ゼロとまったく見分けがつかない。古典的な解決策は、リンクにランダムな重みを与え、ある重みの合計において解がただ一つになるようにすることだ(孤立化補題、isolation lemma)。ところが、偶奇を高速に数える方法は重みを扱えなかった。

著者らの手法を平易な言葉で言えば、次のようになる。

閉路に含まれる矢印を1本推測し、代わりに、その矢印の一方の端からもう一方の端まで、すべての地点を通る経路を探す。
各矢印を確率1/50でランダムに削除する。
各地点で、入ってくる矢印のグループを3つ作り、生き残った各矢印を、空でないランダムなグループの集合にコピーする。
周回路が存在するなら、少なくとも(49/50)ⁿ⁻¹の確率で、各地点から1グループずつ選んで有効な経路の数を奇数にできる。
矢印ごとではなくグループごとにランダムな重みを与える。これで孤立化の手法が使えるようになり、約(50/49)ⁿ回の反復で十分になる。
各反復では、ビョルクルンド、カスキ、クーティスによる行列式の和と、アルヴィンドとグルスワミも用いたランダムな「線形化」を使って、あらゆる重みの合計について奇数か偶数かの数を(15/8)ⁿの時間で計算する。

この2つを掛け合わせると、(50/49)ⁿ × (15/8)ⁿ = (375/196)ⁿ ≈ 1.9133ⁿ となる。

機械が生成した証明

論文の最後には生成AIに関する宣言がある。主定理の証明を生成したのはChatGPT 6 Astraであり、原稿の下書きにも協力したという。著者らは、モデルの元の解法を組合せ論的に読み解く中間命題の主張を用意し、そのうえですべてを検証・修正し、全責任を負うとしている。

この成果は理論的なもので、プログラムは一切実行されていない。またアルゴリズムは乱択的で、どちらの方向にもわずかに誤る可能性がある。一方通行の道の1.9133と双方向の道の1.657のあいだには、まだ大きな隔たりが残っている。