足し合わせて目標になる数を、読むのとほぼ同じ速さで選ぶ

誰にでも言い表せるパズルがある。整数のリスト(たとえば3、9、14、20)と、目標(たとえば23)がある。そのいくつかを選んで、足すと目標にぴったりなるようにできるだろうか(この場合はできる。3 + 20か、9 + 14だ)。これが部分和問題(Subset Sum)で、計算機科学で最も基本的な問題の一つだ。論文はこれを、厳密に解くのが難しいことで知られる問題の族、NP完全問題の基本的な一つとして説明している。

ただし抜け道がある。数があまり大きくなければ、巧妙なアルゴリズムは数の大きさに応じた時間で動く。1957年のベルマンによる古典的な方法は、数の個数nと目標tの積に比例する時間がかかる。それ以来、アルゴリズムは改良され続けてきた。

• ピシンジャー(1999年):n × Nに比例。Nは最大の数。
• ブリングマン(2017年):おおよそn + t。
• いくつかのチーム(2021〜2024年):おおよそn + N^(5/3)、次いでn + N^(3/2)。

究極の目標は、おおよそn + Nの時間、つまり入力を読むのとあまり変わらない時間だった。この分野の研究者は、それをこの一連の研究の「最も重要な未解決問題」と呼んでいた。

目標のすぐ手前まで

中国の浙江大学の陳林(Lin Chen)、毛宇辰(Yuchen Mao)、張国川(Guochuan Zhang)は、n + N^(1+ε)の時間で動くアルゴリズムを示した。εは前もって固定した任意の小さな正の数(0.1、0.01、0.001)でよい。このアルゴリズムは決定的で、負の数や重複した値も受けつけ、数学的な証明がついている。著者らはこの時間をほぼ最適と呼んでいる。

この結果はベクトルにも拡張される。複数の和が同時にそれぞれの目標に一致するように項目を選ぶ問題で、d個の座標についてN^(d+ε)の時間になる。これは、いくつかのグループが提起した整数計画についての問い、つまり変数に上限がある連立方程式の整数解を見つける問題の一部に答える。二つの帰結が明示的に導かれている。数の集合を二つの等しい半分に分けること、そして同一の2台の機械にできるだけ均等に仕事を割り振ることだ。

数をより高い次元に持ち上げる

鍵となるアイデアは幾何学的なものだ。数が密で、目標がありうる和の範囲のかなり内側にあるとき、問題がやさしいことはすでに知られていた。著者らの観察は、疎な数の集合も、より高い次元から見ると密に見えることがある、というものだ。

例として挙げられているのは集合{11, 12, 22, 24}だ。11と22を第1の軸に沿った1歩と2歩、12と24を第2の軸に沿った1歩と2歩として書く。すると、ありうる和は4×4の小さな正方形のすべての点を埋める。しかし、11x + 12yを計算してその正方形を直線に押しつぶすと、和は0から69のあいだに散らばった、すき間で隔てられた七つの塊になる。すき間は射影による錯覚であり、2次元では構造は単純だ。

アルゴリズムは加法的組合せ論の結果を使って、どんな入力に対してもこうした高次元の座標を作る。「埋まった」領域の内部では、答えはただで手に入る。本当に手間がかかるのは縁に近い薄い領域だけで、アルゴリズムはそれをより小さな問題に分け、再帰的に解く。一巡ごとにその領域は大きく縮み、追加される新しい次元はつねに定数個にとどまる。

証明はどう作られたか

論文は「AIに関する免責事項」で始まる。著者らは、この問題の密で多次元的なバージョンについての自分たちの最近の研究をもとに、主な証明の道筋を自ら設計した。そしてAIモデルGPT Astra Ultraを使って、そのアイデアを完全な数学的証明に仕上げた。モデルはいくつかの補題で行き詰まり、それらは著者らのアイデアで解決された。公開された研究ノートに、そのやりとりが記録されている。基本的な乱択アルゴリズムができあがると、モデルはそれを決定的で多次元的なバージョンへと「著者らからの指導なしに」拡張した。モデルは論文の下書きも行い、著者らによれば、証明支援系Lean 4による証明で主な結果を検証した。内容についての全責任は著者らが負っている。

まだゴールそのものではない

指数はちょうど1ではなく1 + εで、εが小さくなるにつれて隠れた定数は大きくなる。次元数への依存性も最適化されていない。著者ら自身、このアルゴリズムを「かなり込み入っている」と述べている。論文は理論的なもので、実装やベンチマークは報告されていない。