アルゴリズム研究の新たな地平、「少しのメモリは多くの時間より強力になりうる」と証明

• MITの理論計算機科学者 Ryan Williams が発表した新たな証明は、メモリ資源が時間よりも強力な計算資源になりうることを示した
• 従来の 時間・空間計算量の関係に関する50年にわたる停滞を破り、あらゆるアルゴリズムをより少ないメモリで動作可能に変換する方法を提示
• 証明の核心は、省メモリシミュレーションを一般化し、アルゴリズムの空間使用量を時間の平方根レベルまで削減するという発想
• これにより、PSPACE と P クラスの違いを定量的に立証するうえで前進があり、さらに大きな隔たりの証明へつながる可能性も開かれた
• 専門家たちはこの成果を「驚くべき進展であり、新たな探求の出発点」と評価しており、今後この結果が理論計算機科学の他の難問を解く手がかりになる可能性がある

---

One Small Step for Space, One Giant Leap for Complexity

Ryan Williamsの新たな証明の概要

• 2024年夏、MITのRyan Williamsは自身の証明を見直す中で、誤りだと思っていたアイデアが実際には有効であることに気づいた
• 彼は、あらゆるアルゴリズムをより少ないメモリで実行可能に変換する一般的な手続きを提案した
• その結果、一部の問題は限られた時間内では解けないことを証明した

時間と空間：計算の二つの資源

• すべてのアルゴリズムは**時間とメモリ（空間）**を使う
• 従来は、特定の問題を解く際には空間が時間に比例すると考えられていた
• Williamsの証明は、空間が時間よりも強力になりうることを数学的に定式化した

理論計算機科学の始まりと歴史

• Juris Hartmanis と Richard Stearns は1960年代に 時間/空間計算量の定義を確立した
• 彼らは、問題を解くのに必要な資源に応じて問題を計算量クラスに分類する基礎を築いた
• P は妥当な時間内で解ける問題、PSPACE は妥当なメモリで解ける問題を表す

最初の進展：1975年のシミュレーション手法

• Hopcroft, Paul, Valiant は、あらゆるアルゴリズムをわずかに少ない空間で動くよう変換する普遍的シミュレーション手続きを開発した
• これは時間と空間の関連性を明らかにする第一歩となったが、その後は限界に突き当たった
• データは同じ空間を同時に占有できないという前提のため、それ以上の進展は不可能だと考えられていた

転換点：Squishy Pebbles

• 2010年、先駆的な計算量理論研究者 Stephen Cook とその同僚たちは、Tree Evaluation - Pebbles and Branching Programs for Tree Evaluation という課題を考案し、ある閾値未満の空間予算しか持たないアルゴリズムではこの課題を解けないことを証明した
  • しかし欠陥があった。その証明は、Paulらが数十年前に用いていたのと同じ常識的な仮定に基づいていた
  • つまり、アルゴリズムはすでに埋まった空間に新しいデータを保存できないということだった
  • 10年以上にわたり、計算量理論家たちはその欠陥を埋めようと努めてきた
• Stephen Cook の息子である James Cook と Ian Mertz は2023年、この従来の前提を破る Tree Evaluation アルゴリズムを発表した Tree Evaluation Is in Space 𝑂 (log 𝑛 · log log 𝑛)
• 彼らは、メモリ内のデータが物理的に重なり合えるという新しい表現モデルを提案した
• この方式は、従来のシミュレーションの限界を克服できる鍵となった

Williamsの決定的な飛躍

• 学生たちの発表をきっかけにCook-Mertzの手法に触れたWilliamsは、これを普遍的シミュレーションに適用するアイデアを思いついた
• 新しいシミュレーションは、アルゴリズムの空間要求量を時間の平方根レベルまで減らせる
• 彼は2025年2月、最終論文を arXivに掲載 し、学界から絶賛を受けた

この結果が意味すること

• この証明は PSPACE > P を直接証明したわけではないが、その方向へ進むための「隙間」を作った決定的な成果である
• 今後この手続きを反復的に適用してより大きな隔たりを作れれば、P vs PSPACE 問題の解決に近づける可能性がある
• これは計算機科学の最も長く続く難問の一つを解く端緒となりうる

余韻を残す結末

• Williamsはこの結果について次のように振り返った
  「本当に証明したかったことそのものは証明できなかったが、最終的に証明できたことは、自分が望んでいたものよりもさらに素晴らしかった。」

[nunojay]

....え?

[GN⁺]

Hacker News のコメント

• 要するに、時間 t で動作するマルチテープ・チューリングマシンは、O(sqrt(t log t)) の空間でシミュレート可能ということ（通常、時間は t より長くかかる） Simulating Time With Square-Root Space
  • Quanta の記事は数学について詩的だったり大げさな表現を混ぜすぎて、誤解を招きやすいのが残念。Quanta の記事では「特定の作業には実行時間に比例するだけの空間が必要だった」と書いているが、複雑性の階層性を見るだけでも、そんな一般的な直感は出てこない。「一部のアルゴリズム」に限った話だけで全体的な直感を作ることはできない
  • 読者に親切すぎるのか、Quanta が複雑性クラス P を「合理的な時間内に解けるすべての問題」とだけ説明し、polynomial という用語自体を使っていないのは少し侮辱的に感じる
• Perl の哲学が込められた “Camel Book” にこんな一節がある: 「メモリが足りなければ買えばいいが、時間が足りないならどうしようもない」 単純に面白い本なので気に入っている
  • この言葉にも両面があると思う。コンピュータのメモリより多くを必要とするプログラムはそもそも今すぐ実行できない一方で、時間がかかってもとにかく実行はできるのだから、時間も結局は重要な資源だ
• あらかじめ計算しておいた値を保存したルックアップテーブルの勝利。以前は、プロセッサが不要になるほどすべての演算を中央に保存できれば、処理速度を革新できるのではないかと思っていた（実際には高速検索という別の難題がある）
  • 昔ストレージシステムの仕事を始めたとき、4KB ブロックを全部あらかじめ計算して保存しておこうというアイデアを出したのだが、固有の 4KB ブロック数は宇宙の原子数より多いと指摘されて驚いた記憶がある
  • HashLife というアルゴリズムは Conway の Game of Life でこれに似たことを Turing 完全に行っている。とても複雑で多様な状態を扱う場合でも、ジャンプするように未来の状態を先回りして計算できるという事実が興味深かった
  • retrieval（検索）ルックアップ自体もキャッシュするというアイデアには問題がない、という冗談
  • コミュニティ単位のキャッシュ、つまりプリコンパイル済みソフトウェアの配布方式で、実際ほぼ実現されている。効率的にコンパイルできないために言語機能を諦めなければならないという従来の障壁も、クラウドでの並列コンパイルと世界規模のキャッシュで乗り越えられる。リリース時に一度だけコンパイルされれば、みんなで使える
  • 「中央にすべての演算を保存できればプロセッサはいらないのでは」という話の延長として、検索履歴そのものまでメモ化してしまおうということ
• Quanta の文体が詩的すぎて、この研究が実際のコンピュータにも応用可能なのか、それとも純粋に理論的なシナリオなのか分かりにくい。より多くのメモリを使う代わりにコンピュータの速度が遅くなる、という意味なのだろうか
• raster グラフィックスプログラミングを長くやってきたので、ルックアップテーブルの活用が自然と身についている。最近は、さまざまな図形をあらかじめ DB に入れておき、クエリごとに最適化された結果を使えるサーバーツールを開発している。複雑ではなく直感的なパターンだ。MIT の教授に特別に教わったわけでもなく、ただ実地で身につけた作業方法だったのに、それが数学的に正当化される証拠を見ると嬉しい。多くのアルゴリズム上のノウハウは、実際には現場の経験から生まれることも多いと思う（例: winding number アルゴリズム）
  • ゲームの最適化で最近得ている成果はどれも、ルックアップテーブルを状況に応じて扱うやり方によるものだ。静的配列だけがルックアップテーブルである必要はなく、時間とともに少しずつ変化するデータも同じように活用できる。GPU で処理する方向に目が開けてきており、コンパイル時またはランタイム時に静的に作られていたテーブルを、実行中に一部だけ変更してテクスチャのように GPU に渡す構造は効率が高い。どこまでをルックアップテーブルと呼ぶのか、その境界は曖昧になってきている
• 空間（メモリ）は時間よりはるかに多くの結果値を表現できる、というのは直感的に感じられる。長さ n のテープでは O(n) 時間のあいだ書き込めるが、2 進テープなら長さ n に 2^n 通りの構成が存在する。空間をうまく使えば、時間に比べてはるかに大きな表現力が得られると思う
  • 私の直感では、1 つのセルに数百回計算した中間結果を保存できる。もし中間結果を保存できず、毎回同じものを再計算しなければならないなら、効率は大きく落ちる。キャッシュヒット率 0% になる状況は非常にまれで、ほとんどの場合は空間を使った効率化が可能だ。逆に、1 回分の時間で数百個のセル分の空間を代替するのは難しく、現在の計算機アーキテクチャでは無限の SIMD は不可能だ
  • O(1) メモリランダムアクセスの仮定があまりに当然視されているが、実際にはコンピュータの規模が大きくなるほどアクセスコストは O(n^(1/3)) まで増える。データセンターではそれを生々しく実感できる。UMA ではなく別のモデルだったはずだ
  • P ≠ PSPACE が証明されていない以上、直感よりも数学的に立証するほうが難しい領域だ
  • 一方でその通りではあるが、並列化が難しい問題（例: alternating machine PTIME=PSPACE）では、空間が大きな利得をもたらさないこともある。論文では t/log t から sqrt(t log t) への飛躍が革新的だが、無限並列化でも乗り越えられない実体的な限界はあるはずだ
  • 実務では作業の性質によって変わる。代入演算よりストレージアクセスのほうがはるかに遅いときは、再計算したほうが速いこともある
• 時間と空間の「トレードオフ」は、一方の資源を制限したとき、他方の最適値を必ずしも得られない現象として説明できる。たとえばソートアルゴリズムで時間・空間・安定性という 3 つの制約があるとき、安定性まで満たそうとすると、かえって時間や空間の効率が落ちる。現時点では、不安定ソートと同じくらい速く、かつメモリ使用量も少ない安定ソートはない
• Quanta Magazine の記事スタイルは個人的には好きだ。コンピュータ科学者だけでなく、関連分野に関心のある一般の人にまで視野を広げてくれる。俯瞰的な見取り図と親しみやすい説明の仕方が、新しい視点やアイデアを与えてくれるきっかけになる
• Ryan Williams の講演と論文へのリンクを共有
• single-tape チューリングマシンが入力として 2 進数 N を受け取り、テープの右側に 1 を N 個書こうとすると、時間 N で N マスの空間が必要に見える。それなのに、どうやって N より少ない空間でこれをシミュレートできるのか気になる。テープの任意の位置にジャンプできないチューリングマシンの構造上の性質を考えると、実際のコンピュータとの関係がどうなっているのかも気になる
  • マルチテープ・チューリングマシンは単一テープよりかなり高速で、ここで言う「空間」は入力・出力を除いた一時的な作業領域のことだ
  • 論文の主な対象は決定問題で、出力が 1 ビットしか必要ない状況だけを考えている。出力が N ビットなら、実質的には N 個の決定問題をつなげたのと同じだという説明だった