禁じられた比較があっても、ほぼ同じ速さで並べ替える
n個のものを2つずつ比べて順に並べるには、約n log n回の比較が必要であり、それで十分でもある。ただしそれは、どの2つも比べられるという前提での話だ。
実際には、比べられないことが多い。著者らは2011年の論文から例を借りている。複数の候補者が同じ仕事に応募し、それぞれに推薦者がいる。2人の候補者を比べられるのは、両方を知る推薦者がいる場合だけだ。許された比較はネットワーク、つまりグラフをなす。各要素は1つの点、許された各比較は1本のリンクである。真の順序は隠れているが、グラフがそれを含むことは保証されている。各要素を次の要素へとつなぐ道としてだ。問いは、順序を取り戻すのに何回の比較が必要か。これが一般化ソート(generalized sorting)である。
いつもの手が通用しない理由
古典的なアルゴリズムは、選択の自由に頼っている。クイックソートは「ピボット」を選び、それをほかの大半の要素と比べるが、任意のグラフには、他の大半と結ばれた要素が1つもないかもしれない。マージソートは要素をグループに分けてそれぞれを並べ替えるが、あるグループは単独では並べ替えられないかもしれない。最終的な順序で隣り合う2つの要素が、そのグループの中で結ばれているとは限らないからだ。より根本的には、通常の並べ替えでは、ありうる順序のかなりの割合を排除する比較が常に手元にある。比較が制限されていると、そうした比較が1つもないこともありうる。
進展は遅かった。2011年、Zhiyi Huang、Sampath Kannan、Sanjeev Khannaは、対数因子を除いて約n¹·⁵回の比較を用いる方法を見つけ、以来この上界は任意のグラフに対して破られずにきた。3人は、この問題が通常の並べ替えより本質的に難しく、nの1より大きな累乗の回数を必要とするのではないかとさえ問いかけた。
まず予測し、あとで直す
ニューヨーク大学のSanjeev Khanna、ハーバード大学のAaron Putterman、同じくニューヨーク大学のJunkai Songは、いまこの問いに「否」と答える。3人の乱択アルゴリズムは、どんなグラフでも平均約n log⁴ n回の比較で並べ替える。通常の並べ替えより、対数因子がいくつか多いだけだ。しかも3人によれば、それは「比較的単純」だという。ただし、この利得は理論上のものだ。証明に現れる定数は巨大で(2³²のような因子)、利点が現れるのはnが非常に大きいときに限られる。
このアルゴリズムは既知の結果の上に築かれている。誰かがすべてのリンクの向きについて推測を渡してくれて、そのうちw本が間違っているなら、約n log n + w回の比較で順序を取り戻せる。そこで課題は、少ない比較で、誤りの少ない推測を作ることになる。主な手順は次のとおりだ。
- 大まかな最初の推測。 リンクで結ばれた組を無作為に抽出して比べ、答えと矛盾しない順序を何でもよいから1つ選ぶ。誤りは多いが、多すぎはしない。
- 誤りを直すのではなく、隔離する。 間違った推測を訂正する代わりに、アルゴリズムは誤りが平均より密集しているグラフの部分を見つけ、脇によけておく。各ラウンドで、残る誤りは期待値で4分の1に減る。
- あとで戻ってくる。 脇によけたリンクは、後の段階で処理される。各段階でまだ保留中のリンクの少なくとも半分が片づくので、100万本のリンクなら約20段階で足りる。
機械とともに見つけた証明
この論文のAI利用の開示は、異例なほど詳細だ。ChatGPT 6-Astraは「改善された上界の証明に不可欠だった」と記されている。あるモデルがまず約n¹·³³回の比較を用いるアルゴリズムを見つけ、そこで行き詰まった。著者らはそれをn¹·²まで押し進めた。その後、数週間にわたって何十回もプロンプトを与えられたモデルたちが、n^(10/9)、n^(17/16)、n^(19/18)と次々に改善を見つけ、ほぼ線形のアルゴリズムにたどり着いた。著者らは、自分たちの中間段階がその最終的な発見に不可欠だったかどうかははっきりしない、と付け加えている。
まだ開かれている問い
この結果が数えるのは比較の回数であって、計算時間ではない。現在の形では、このアルゴリズムは多項式時間では動かない。2011年の方法は多項式時間で動いていた。著者らは3つの未解決問題を挙げる。残る対数因子を取り除けるか、乱択を使わないアルゴリズムで同じ性能が出せるか、そして効率的なアルゴリズムで同じ比較回数に達せるか、あるいはそもそもn¹·⁵を破れるか、である。
