計算機科学・AIプレプリント理論1分で読めます

クリーク探しの速度制限が40年ぶりに破られる

n人がいるソーシャルネットワークを思い浮かべてほしい。その中に、全員が互いに知り合いであるk人のグループはあるだろうか。計算機科学者はそのようなグループをk-クリークと呼び、それを見つけることは、数えきれないほどの応用をもつ古典的な問題だ。素朴なやり方は、k人のありうるグループをすべて調べる。その数はおよそn^k個で、大きなネットワークでは絶望的だ。

1985年の技と長い挑戦

40年以上前、Jaroslav NešetřilとSvatopluk Poljakが近道を見つけた。2人はk-クリークの探索を、より大きなグラフの中での三角形の探索に変えた。そしてその三角形探しは、大きな数の表である行列の掛け算によって行える。コストは行列の掛け算の指数ωに依存し、2人の方法はおよそ n^(ωk/3) ステップかかる。ωの正確な値は誰も知らない。少なくとも2であり、論文は最近の上界として9/4を挙げている。

この1985年の方法の指数は、一度も破られなかった。2004年、Gerhard Woegingerは、ある固定したkについてもっとうまくやるよう研究者たちに挑んだ。それから20年以上が過ぎた。そのあいだに、k-クリーク仮説(k-Clique Hypothesis)、つまりn^(ωk/3)が本質的に最善であるという仮説は、「細粒度計算量理論」(fine-grained complexity)の基礎となった。研究者たちはこの仮説を使って、文法の構文解析から圧縮データの解析まで、ほかの多くの問題もより速くは解けないと論じた。

動く標的

この仮説を反証するには、特別な難しさがあった。仮説が予測するコストはωに依存するが、ωはわかっていない。現在のωの最良の値に勝つアルゴリズムも、のちに誰かがより速い行列の掛け算を見つければ、仮説に勝てなくなるかもしれない。

MITのVirginia Vassilevska Williamsとテルアビブ大学のOr Zamirは、この問題を回避する。2人は、十分に大きなすべてのkについて、k-クリークをおよそ n^((ω/3 − c)k) ステップで見つけられる、さらには数えられることを証明した。ここでcは、kにもωにもよらない正の定数である。この節約は、ωの真の値が何であれ、その値に対して測られる。ω = 2、つまり考えうる最良の場合でさえ、節約は生き残る。

くさびを折りたたむ

この方法の核心は、9頂点のパターンに関わる。標準的なやり方では、それらを3個ずつ3つのグループに分け、3つの巨大な行列を掛け合わせる。著者らはくさび(wedge)、つまり1つの頂点を共有する2本の辺に注目し、2つの行列のあいだに、何も変えない表、すなわち単位行列を差し込む。そしてその単位行列を、いくつかの「入れ替え」と低ランクの残りの和として書く。それぞれの入れ替えは、くさびの2本の辺を1本に合体させる。

入れ替えからは、辺の少ないより単純なパターンが得られ、それらは同じ方法でふたたび処理される。9頂点のパターンの辺は多くても36本なので、この再帰は終わる。低ランクの残りは、掛け合わせる行列を小さくする。ω = 2のときでも改善を保てるのは、この技を2つの別々のくさびに同時に適用するからだ。そのうえで、9の倍数であるどんなkも、9つのブロックにまとめることができる。

現実の、しかしごくわずかな改善

著者らは改善の数値を示していない。定数は「最適化なしではきわめて微小、大幅な最適化をしてもごくわずか」の範囲にあると説明している。要点は実際の速さではない。数十年にわたって信じられてきた壁が存在しないということだ。

その影響はクリークの先にまで及ぶ。Max-CutやMax-2-SATのような難しい最適化問題に対する厳密アルゴリズムは、n個の変数に対しておよそ2^(ωn/3)ステップかかっていたが、これも指数が小さくなる。固定した任意の小さなグラフのコピーを数える問題も同様だ。

AIがしたこと

著者らは専用の節で、一般向けのウェブインターフェースを通じて使ったChatGPT-6とどのように作業したかを説明している。5人のクリークについての自分たちのアイデアと、別の予想である指数時間仮説(Exponential Time Hypothesis)を反証した最近のOpenAIの成果を出発点に、このモデルは5-クリークについて、最初の、複雑な改善を見つけた。著者らはそれを、AIの助けを借りて、証明の核心にある代数的分解へと抽出した。この分解を2人は「ほぼ純粋にAIの貢献」とみなしている。そのまわりに築かれたアルゴリズムの枠組みは、おもに自分たちのものだと2人は言う。

ある指摘が目を引く。AIが生成したわかりにくい証明は人間には読みにくい、と著者らは述べる。そして著者らは、「それがAI自身にとっても理解しにくいことに感銘を受けた」という。