著者：Ben Brubaker
Synced Review翻訳
プログラムを実行中にコンピュータがフリーズしてしまい、最悪の場合ファイルを再作成しなければならなかったり、スマートフォンの「メモリ不足」警告が頻繁に表示され、大切な写真やアプリを泣く泣く削除せざるを得なかったり、という経験は誰にでもあるはずです。
これらの日常の煩わしさは、実は計算の世界における2つの極めて重要な基本要素、すなわち時間と空間に集約されます。
時間と空間（メモリとも呼ばれる）は、計算における最も基本的な2つのリソースです。どのようなアルゴリズムも、実行には一定の時間を要し、実行中にデータを保存するために一定の空間を占有します。
これまで知られていた特定のタスクのアルゴリズムは、必要な空間が実行時間にほぼ比例するとされ、研究者たちは長らくこの点を改善できないと広く考えていました。
MITの理論計算機科学者Ryan Williamsの最新の研究は、任意のアルゴリズム—それがどのようなタスクを実行するかにかかわらず—を、著しく少ない空間しか占有しない形式に変換できる数学的手順を確立しました。これは、理論上、少量の計算メモリ（空間）が大量の計算時間よりも価値があることを証明し、コンピュータ科学者たちの約50年間の認識を覆しました。
論文タイトル：Simulating Time With Square-Root Space
論文アドレス：https://arxiv.org/pdf/2502.17779
さらに重要なことに、この結果は特定の空間制約下で実行可能な計算の範囲を明らかにするだけでなく、限られた時間内では完了できない計算の種類を間接的に証明しました。後者は以前から予想されていましたが、厳密な証明方法が欠けていました。
50年間の探求と限界
Juris Hartmanis
1965年、Juris HartmanisとRichard Stearnsの両名は共同で2つの画期的な論文を発表し、「時間」（Time）と「空間」（Space）という2つの概念に初めて厳密な数学的定義を確立しました。
論文アドレス：https://doi.org/10.1090/S0002-9947-1965-0170805-7
これらの定義は研究者たちに共通の言語を提供し、両種類のリソースを比較し、それに基づいて問題を異なる複雑性クラス（complexity classes）に分類することを可能にしました。
最も重要な複雑性クラスの一つであるPクラスは、大まかに言えば、合理的な時間内に解決できるすべての問題を含みます。それに対応する空間複雑度クラスはPSPACEクラスと呼ばれます。
これら2つのクラス間の関係は、複雑性理論の中核的な問題の一つです。
Pクラスに属するすべての問題はPSPACEクラスにも属します。これは、高速アルゴリズムが実行時に大量のコンピュータメモリ空間を使用するのに十分な時間がないためです。逆に、すべてのPSPACEクラスの問題も高速アルゴリズムで解決できるとすれば、両方のクラスは完全に等価となり、計算時間と計算空間は能力において本質的な違いがないことになります。
しかし、複雑性理論の研究者たちは、PSPACEクラスははるかに規模が大きく、Pクラスに属さない多くの問題が含まれていると広く考えています。言い換えれば、彼らは、計算能力の観点から見ると、空間は時間よりもはるかに強力なリソースであると信じています。この信念は、アルゴリズムが同じ小さなメモリブロックを繰り返し使用できるのに対し、時間は再利用できない—一度過ぎ去れば戻ってこない—という事実に基づいています。
しかし、複雑性理論家たちは、このような直感的な推論では満足しませんでした。彼らは厳密な数学的証明を必要としました。PSPACEクラスがPクラスよりも厳密に大きいことを証明するためには、研究者たちは、本質的に高速アルゴリズムでは解決できないPSPACE内の特定の問題が存在することを示す必要がありました。
1975年、John Hopcroft、Wolfgang Paul、およびLeslie Valiantは、汎用的な「シミュレーションプログラム」を設計し、特定の時間内に完了する任意のタスクが、その時間よりもわずかに少ない空間で完了できることを証明しました。これは時間と空間を結びつける最初の重要なステップであり、空間が時間よりも少なくともわずかに強力であることを示しました。
しかし、その後研究の進展は停滞し、複雑性理論学者たちは、根本的な障害にぶつかったのかもしれないと疑い始めました。
問題は、Hopcroft、Paul、Valiantが提案したシミュレーション手法の「汎用性」という特徴にありました。多くの問題は、その時間予算よりもはるかに少ない空間で確かに解決できましたが、一部の問題は、直感的には、時間とほぼ同等の空間を必要とするように見えました。もしそのような状況が実際に存在するならば、より効率的な空間節約型汎用シミュレーションは考えられません。
その直後、Paulは他の2人の研究者とともに、この点を証明しました。すなわち、より効率的な汎用シミュレーションは確かに不可能であるということを、異なるデータブロックが同時に同じメモリ空間を占有できないという、一見すると当然の前提を採用すれば、示したのです。
Paulの研究結果は、PとPSPACEの関係問題（P versus PSPACE problem）を真に解決するためには、シミュレーションを中心とした研究経路を完全に放棄し、全く新しい理論的手法を探す必要があることを示唆しました。問題は、当時、実行可能な代替案を提案できる者がいなかったことです。
この研究課題は、それから丸50年間膠着状態に陥り、Williamsの研究が最終的にこの行き詰まりを打破するまで続きました。
膠着状態を打ち破る
Williamsの新しい研究は、計算におけるメモリ使用に関する別の問題、すなわち「極めて限られた空間でどのような問題が解決できるのか」という問題における画期的な進展に端を発しています。
2010年、複雑性理論の先駆者Stephen Cookと彼の共同研究者たちは、ツリー評価問題（tree evaluation problem）と呼ばれる新しいタスクを設計し、特定の閾値以下の空間予算に制約されるいかなるアルゴリズムもこの問題を解決できないことを証明しました。
しかし、この証明には一つの抜け穴がありました。その推論は、Paulらが数十年前から提示していた直感的な仮定、すなわちアルゴリズムは新しいデータをすでに占有されているメモリ空間に保存できない、というものに依拠していたのです。
その後10年以上にわたり、複雑性理論の研究者たちはこの抜け穴を埋めようと試みてきました。2023年になって、Stephen Cookの息子James Cookと研究者のIan Mertzがこの仮定を覆しました。彼らは、ツリー評価問題を以前考えられていたよりもはるかに低い空間コストで解決できる、全く新しいアルゴリズムを設計したのです。この結果により、元の下限証明は完全に無効となりました。
Cook（左）とMertz（右）
元々Stephen Cookの証明仮定では、情報ビット（bit）は「小石」（pebbles）のように扱われ、アルゴリズムのメモリ内の異なる場所に配置されなければならないと考えられていました。しかし、データ格納の方法はこれよりもはるかに柔軟であることが判明したのです。
Williamsの革命的飛躍
CookとMertzが提案したアルゴリズムは多くの研究者の興味を惹きましたが、当初、それがツリー評価問題（tree evaluation problem）以外の他のシナリオにも適用できるかどうかは不明でした。
Ryan Williams
2024年春、Ryan Williamsが教える授業で、ある学生グループがCookとMertzの論文を期末プロジェクトとして発表しました。学生たちの熱意が彼の興味を刺激し、この研究を深く掘り下げることを決意させました。
着手するとすぐに、彼はある重要なアイデアを掴みました。CookとMertzが提案した方法が本質的に汎用的な空間圧縮ツールであると認識したのです。彼は、このツールを利用して、時間と空間の複雑性をより優れた形で結びつける新しい汎用シミュレーションメカニズム（universal simulation）を設計できないか、と考えました。それは、かつてHopcroft、Paul、Valiantが構築したモデルと同じように、しかしより高性能なものでした。
その古典的な成果は、与えられた時間予算（time budget）を持つ任意のアルゴリズムを、わずかに少ない空間予算を持つ新しいアルゴリズムに変換する方法を提供しました。Williamsは、もし「柔らかな小石」（squishy pebbles）に基づいたシミュレーション技術を構築すれば、変換後の新しいアルゴリズムが必要とする空間は、当初の時間予算の平方根にほぼ等しい、はるかに大幅に削減されることを認識しました。
この新しいタイプの省スペースアルゴリズムは、演算速度が著しく低下するため、実際の応用はあまり期待できません。しかし、理論的な観点から見ると、その意義は革命的な突破と言えるでしょう。
Williamsのシミュレーション手法は、既存の概念である「ブロック遵守チューリングマシンシミュレーション」（block-respecting Turing machine simulation）から出発し、それを拡張しました。その基本的な考え方は、計算プロセス全体（合計tステップと仮定）をt/b個の連続する「計算ブロック」（computation blocks）に分解し、各ブロックがb個の計算ステップを含むようにすることです。
これらの「計算ブロック」の入力/出力状態（または「構成」と呼ばれる）の間には依存関係があり、これにより「計算グラフ」（computation graph）を形成できます。
Williamsの重要なステップは、このチューリングマシンがtステップ内で行う計算問題—特にその最終状態や出力を判断すること—を、「ツリー評価問題」（Tree Evaluation Problem, TEP）のインスタンスに帰着（reduce）させることです。
この構築されたツリー評価問題のインスタンスは、特定のパラメータを持っています。ツリーの高さhは、ほぼt/b（つまり計算ブロックの数）であり、各ノードが伝達する情報のビット長はb、ツリーのファンイン度（各ノードが持つ子ノードの数）はd（チューリングマシン自体に依存する小さな定数）です。
重要なのは、この「ツリー」が「暗黙的に定義されている」という点です。これは、メモリ内で実際にツリー全体を構築する必要がなく、代わりにいつでもツリーのどの部分がどのようなものになるべきかを決定できる一連の規則があることを意味します。
この構築された「ツリー評価問題」のインスタンスに対して、WilliamsはCookとMertzが提案したアルゴリズムを適用して解を求めました。Cook-Mertzアルゴリズムがこの種のツリー評価問題を解決する空間複雑度は、およそd^(h/2) * poly(b, h)です（ここでdはファンイン度、hはツリーの高さ、bはビット長です）。
Williamsは続けて総空間複雑度を分析し、「計算ブロック」のサイズbを慎重に選択することで最適化を行いました。パラメータbが約√t（総計算時間tの平方根）に設定されると、前述のツリーの高さh（約t/b）も約√tになります。
これをCook-Mertzアルゴリズムの空間複雑度式（特にd^(h/2)の項）に代入し、他の要因（ポインタやカウンタなどの記録に由来するlog t因子など）を総合すると、最終的に総シミュレーション空間複雑度はO(√t log t)と導出されます。
参考リンク：
https://www.quantamagazine.org/for-algorithms-a-little-memory-outweighs-a-lot-of-time-20250521/
https://arxiv.org/pdf/2502.17779
© THE END
転載をご希望の場合は、本公式アカウントにご連絡の上、許可を得てください。
寄稿または取材のご依頼：liyazhou@jiqizhixin.com