借りた満杯のディスクがコンピューターを速くする

時間はかからないがメモリを大量に食う問題もあれば、その逆の問題もある。いくつかの基本的な課題について、理論家たちはこのトレードオフに厳しい限界があることを証明してきた。作業用メモリが小さければ、速くはできないというのだ。新しい論文は、ある奇妙な資源、つまりすでに満杯で、無傷のまま返さなければならないメモリが、その限界を打ち破ることを示した。

借りたハードディスク

このモデルは触媒的計算（catalytic computing）と呼ばれ、2014年にBuhrman、Cleve、Koucký、Loff、Speelmanによって導入された。アルゴリズムには、大きさnの入力に対してlog nビット程度の、ごく小さなきれいなメモリが与えられる。それに加えて、自分が選んだわけではない任意のデータですでに埋まった、巨大な汚れたメモリも与えられる。どちらも好きなように使ってよいが、停止するときには、汚れたメモリのすべてのビットが元とまったく同じでなければならない。

著者らは定番のたとえを使う。計算をするために、大切なデジタルの思い出が詰まった友人の巨大なハードディスクを借りる。友人を失いたくはないので、終わったらすべてのビットを元に戻す。

このモデルは当初、そんなメモリは役に立たないことを証明するためのものだった。直感的には、すべてを元に戻すにはすべての情報を保持しておく必要があり、空きはまったく生まれないはずだ。ところが驚いたことに、実際はその逆だった。満杯のメモリがあれば、きれいなメモリだけでは誰も解き方を知らない問題が解けるのだ。ただし、それらの結果は空間に関するもので、アルゴリズムは極端に遅かった。

証明上可能な限界より速く

MITのAdelmo Morrison Orozco、Nathan Sheffield、Ryan Williamsは今回、速さに目を向けた。対数サイズのきれいなメモリと、多項式サイズの借りたメモリを使って、彼らは次のことができるアルゴリズムを示した。

• リストの並べ替えと離散フーリエ変換の計算を、ほぼ線形の時間 n^(1+o(1)) で行う。
• 行列の掛け算を、メモリ無制限で知られている最良の方法と同じ速さの時間 n^(ω+o(1)) で行う。

借りたディスクがなければ、時間とメモリの積は、並べ替えとフーリエ変換では少なくともn²のオーダー、行列の掛け算ではn³のオーダーでなければならないことが証明されている。つまり、これらの触媒的アルゴリズムは、小さなメモリしか持たない普通のアルゴリズムには到達できない速さに達している。著者らはこれを、触媒的アルゴリズムが非触媒的なアルゴリズムを上回ることを無条件に示した初めての例だとしている。

切り替え、読み取り、元に戻す

鍵となるのは、短い組合せ論的なトリックだ。あるアルゴリズムが、借りたメモリの一部を、未知の値τと、τ + xとの間で切り替えられるとする。ここでxは、知りたい結果だ。同じく借りものの大きな「補助」テーブルの中で、注意深く選んだ一群の項目に1を足す。すると、位置τにある項目は、xがある集合に属する場合に限り1増える。その後すべての手順を逆に実行すれば、ディスクは元どおりになり、欲しかった答えの1ビットだけが残る。

このトリックを層ごとに積み重ねると、浅い回路を素早く評価できる。著者らは、並べ替えネットワーク、高速フーリエ変換、高速行列乗算を、こうした回路として書き直した。算術演算では、未知の値どうしを掛け合わせる層だけに余分なコストがかかり、純粋に線形な層はほとんどただで済む。

公平な比較

一つの反論がある。古典的な限界は、答えが別の出力テープに左から右へ一度だけ書き込まれることを前提としている。ところが触媒的アルゴリズムは、答えを借りたディスクに書き込む。論文はこの点にも答えている。著者らは、自分たちのアルゴリズムが出力テープ上を2回たどることで答えを書き出せること、そして普通のアルゴリズムにとって2回たどっても1回の場合と比べて何の得にもならないことを示した。したがって限界はそのまま当てはまり、両者の差は保たれる。さらに、借りたディスクがあっても1回では不十分であることも証明した。その場合、並べ替えは同じn²の壁にぶつかる。

恩恵を受ける長いリスト

同じ道具を使えば、大きな整数や多項式の掛け算、ネットワーク内の三角形の数え上げやクリークの発見、経路や閉路の検出、ワイルドカードを含む文字列パターンの照合についても、高速な触媒的アルゴリズムが得られる。その実行時間は、小さな因子を除けば、メモリを好きなだけ使える最良の既知アルゴリズムと一致する。どの場合でも、借りたメモリは貸されたときとまったく同じ状態で返さなければならない。