TIME [t] \subseteq SPACE [t lo g t]

t歩の計算は、ほぼ√tの記憶で足りる（ウィリアムズの定理）

Simulating time with square-root space (Williams's theorem)

著者自身が「とても意外だ」と書いた、50年ぶりの改良。

多テープチューリング機械でt歩の計算は、t log tの平方根ほどの記憶で足りる。2025年にウィリアムズが、1975年のt/log tを大きく下げた。

年代: 1975〜2025年
習う: 大3以上・情報科学・計算量理論
レベル: 大学(例題 5 問)
人物: ライアン・ウィリアムズ、ジョン・ホップクロフト、ヴォルフガング・パウル、レスリー・ヴァリアント、ジェームズ・クック、イアン・マーツ

情報科学数学工学

逸話

0.99乗でも足りないはずだった

$t$ 歩かかる計算をまねるには、 $t$ に近い量の記憶が要る。 $t^{0.99}$ マスでも足りない。理論計算機科学では、数十年のあいだ広く信じられてきたらしい。その見方を2025年に崩したライアン・ウィリアムズが、論文の序論でそう振り返っている。

記憶が $t$ マスほどあれば足りることは、すぐに分かる。1歩でヘッドが書きかえるマスは、テープごとに1つしかないからだ。難しいのは、それよりずっと少ない記憶で同じ答えを出せるかどうかである。

2025年2月に出た答えは、ほぼ平方根だった。

マサチューセッツ工科大学（MIT）のウィリアムズ教授は、多テープチューリング機械で $t$ 歩かかる計算なら、どれもおよそ $t lo g t$ の記憶でシミュレートできることを示した。シミュレートするとは、同じ入力に同じ答えを出す別の手順でまねることだ。論文は2月24日に計算量理論のプレプリントサーバーECCCで、翌日にはarXivでも公開された。定数倍を無視して比べると、100万歩の計算では、1975年から続いた上界 $t / lo g_{2} t$ は約5万マス、新しい上界は約4,500マスになる。

ウィリアムズは論文に「定理1.1は、とても意外だと思う」と書いた。前段に置いた少し弱い $O (t lo g t)$ の結果にも、「（著者にとって）すでに極めて意外だ」と書き添えている。

ライアン・ウィリアムズ21世紀に活躍t歩の計算を、ほぼ√tの記憶でシミュレートできることを示した

では、なぜ50年も手が届かなかったのだろうか。

鍵は、まったく別の問題のために磨かれてきた手順にあった。2023年にジェームズ・クックとイアン・マーツが示した、木の評価問題を少ない記憶で解く方法である。ウィリアムズは論文の最後の節で、この手順が先に見つかっていたことを「幸運だった」と書いている。計算を木の評価に置き換える自分の帰着が先だったら、研究者たちは著者も含めて、それを木の評価の研究を阻む「壁」とみなしただろう。この方向の研究を思いとどまらせたかもしれない、という。

同じ帰着が、見つかる順番しだいで壁にもなりえた。

2025年3月、ウィリアムズはプリンストン高等研究所でこの結果を話した。6月にはプラハで開かれた理論計算機科学の国際会議STOC 2025で、最優秀論文賞の4本に選ばれている。同じ4本には、最短経路の「並べ替えの壁」を破った段然らの論文も入った。

冬の木立が窓の外に見えるセミナー室で、聴衆の後ろ姿の先、黒板の前に小さく立つ講演者(画像生成 AI で描いたイメージ) — 2025年3月、プリンストン高等研究所で結果を話した（本人の経歴書による）画像生成AIで描いたイメージ

起源

1975年の小石と、2023年の木

読み書きできるテープが1本だけの機械なら、平方根の答えは早くからあった。1968年、ジョン・ホップクロフトとジェフリー・ウルマンは、そうした機械で $t$ 歩かかる計算を、 $t$ ほどの記憶でシミュレートできることを示している。ところがテープが何本もある機械では、平方根の上界は2025年まで知られていなかった。

多テープの機械については、1975年10月の国際会議FOCSで、ホップクロフト、ヴォルフガング・パウル、レスリー・ヴァリアントの3人が、記憶を $t / lo g t$ まで減らせることを示し、1977年に学術誌にも論文を載せた。

3人は、計算を同じ長さの区切りに分け、どの区切りがどの区切りの結果を使うかをグラフに描いた。そのうえで、グラフの点に小石を置いたり外したりする一人遊び（ペブルゲーム）として、記憶を数えた。小石を置いた点の結果だけを覚え、外した点は要るときに計算し直す。点が $n$ 個で、各点に入る辺が $d$ 本以下のグラフなら、小石は $c (d) n / lo g n$ 個で足りる。

この数は、グラフによってはそれ以上減らせない。1976年には、パウルとロバート・タージャン、J・R・セロニが、小石が $n / lo g n$ の定数倍ほど要るグラフがあることを示している。ウィリアムズによると、こうした小石の下限は、1975年の結果を改良するうえで大きな障害だった。

ジョン・ホップクロフト20世紀後半から活躍1975年、t歩の計算をt/log tの記憶でシミュレートする方法を示した

ホップクロフトは1967年にコーネル大学へ移り、いまも名誉教授として籍を置く。2025年10月9日、そのコーネル大学のゲイツ・ホールで、卒業生のウィリアムズが講演している。要旨によると、「1970年代にコーネルでなされた仕事」と、ここ2年の新しい考えを使って、時間と記憶の新しい関係を示す講演だった。

紅葉した木々が大きな窓の外に見える講義室で、段になった席の聴衆の後ろ姿と、遠くのスクリーンの横に立つ講演者(画像生成 AI で描いたイメージ) — 2025年10月9日、母校コーネル大学のゲイツ・ホールで講演した（大学の告知による）画像生成AIで描いたイメージ

では、ここ2年の新しい考えとは何だったのか。

出発点は、別の大問題のために作られた問題だ。2009年、スティーブン・クックらは木の評価問題を考えた。高さ $h$ の二分木があり、葉には $b$ ビットの値が書かれている。内側の点には、2つの子の値を受け取って自分の値を返す関数が、表の形で与えられる。根の値を求めればよい。

素直に解くなら、片方の子の値を覚えたまま、もう片方の部分木を計算する。段ごとに $b$ ビットずつ覚えるので、記憶は $h \cdot b$ ほどになる。クックらは、これより大幅には減らせないと予想した。予想が正しければ、対数の記憶で解ける問題のクラスLと、多項式時間で解ける問題のクラスPが違うことになる。

この直観に疑いを向けたのが、2014年にハリー・ブールマンらが考えた触媒計算である。中身の分からないデータで埋まった記憶を借りてよいが、計算が終わったら1ビットも違わず元に戻さなければならない。そんな窮屈な約束の下でも、借りた記憶が計算の役に立つことがあると、ブールマンらは示した。木の中で古い値を覚えた記憶は新しい値の計算に使えない、という前提を疑うための計算モデルだった、とクックとマーツは書いている。

ジェームズ・クックとイアン・マーツは、2020年からこの考えを木の評価に持ち込んだ。2023年11月の論文では、記憶を $O (lo g n \cdot lo g lo g n)$ まで減らしている。 $n$ は入力の長さで、対数の記憶との差は $lo g lo g n$ 倍しか残っていない。論文は翌年6月、バンクーバーで開かれたSTOC 2024で発表された。ウィリアムズはこの手順を、木ではなく、時間のかかる計算そのものに当てはめた。

証明

借りた記憶でたどる区切りの木

多テープチューリング機械 $M$ が、長さ $n$ の入力に $t$ 歩で答えを出すとする（ $t \geq n$ ）。テープの本数は $M$ で決まる定数である。以下は論文の第3章の筋で、計算グラフの推測と「失敗」の伝え方などの細部は省く。

1歩でヘッドが書きかえるマスはテープごとに1つなので、使う記憶は $O (t)$ を超えない。
$TIME [t] \subseteq SPACE [t]$
時間を $b$ 歩ずつの区切りに、テープを $b$ マスずつの区画に分ける。1975年の3人の補題によると、 $M$ はテープを1本足し、時間を定数倍にするだけで、どの区切りのあいだも各ヘッドが1つの区画にとどまる機械に作り直せる。作り直した機械のテープを $p$ 本とする。区切りの数は次のとおり。
$B = O (\frac{t}{b})$
時間をb歩ずつに区切ると、区切り5の計算に要るのは、直前の区切り4と、同じ区画を最後に触った区切り2の結果だけになる。
区切り $j$ の終わりの様子（状態、ヘッドの位置、触った区画の中身）を $content (j)$ と書く。長さは $O (b)$ ビットで、直前の区切りと、各ヘッドがいまの区画を最後に触った区切りの結果から、 $b$ 歩動かせば求まる。使う区切りは $d = 2 p$ 個以下である。
$content (j) = F_{j} (content (i_{1}), \dots, content (i_{d}))$
最後の区切りを根にし、各点の子にその点が使う区切りを置くと、グラフは木に開ける。根の値から受理か拒否かが分かり、葉は入力か空白の区画になる。木の点は指数関数的に多いが、ヘッドが区画を左右どちらへ移ったかの印（ $- 1$ , $0$ , $1$ ）を区切りごとに覚えておけば、どの点の子も少ない記憶で求まる。印は前もって分からないので、 $O (B)$ ビットの候補を順に試し、合わない候補では根が「失敗」になるように関数を作る。
$木の高さ h \leq B + 1, 各点の値 O (b) ビット$
この木を深さ優先で素直にたどると、段ごとに子の値を覚えるので、記憶は減らない。
$h \cdot b = O (t)$
クックとマーツの手順は、高さ $h$ 、子の数が $d$ 以下、値が $b$ ビットの木の根を、次の記憶で求める。
$O (d b + h lo g (d b))$
この手順は、子の値を新しい場所に覚えない。中身の分からない共有の場所 $x^$ に子の値 $v$ を足して使い、使い終えたら同じ $v$ をもう一度足して消す。標数2の有限体では、同じものを2回足すと0になるからだ。値の取り出しには、次数が $m$ より小さい多項式 $P$ と、1の原始 $m$ 乗根 $ω$ について成り立つ等式を使う。 $m$ は体の元の数より1小さい数である。
$i = 1 \sum m P (ω^{i} x^+ v) = P (v)$
段ごとに残すのは、いまどの子を扱っているかと、和の何項目まで来たかを表す $O (lo g (d b))$ ビットだけになる。 $d$ は定数で $h = O (t / b)$ なので、印の候補の $O (t / b)$ ビットも足すと、記憶は次の大きさになる。
$S (b) = O (b + \frac{t}{b} lo g b)$
$b = t lo g t$ とおくと、2つの項はどちらも $t lo g t$ ほどにそろう（次の章で確かめる）。
$TIME [t] \subseteq SPACE [t lo g t]$

このシミュレーションは、記憶を削る代わりに時間を惜しまない。論文によると、 $b$ 歩の区切りを多項式に置き換えて1点の値を求めるだけで、 $2^{Θ (b)}$ の時間がかかる。速いプログラムを作る定理ではなく、記憶だけで測ったときの限界を示す定理である。

手順3と手順4は、ヘッドが隣の区画へしか移れないことを使っている。好きな番地を一度に読めるランダムアクセスの機械では、 $t^{0.99}$ の記憶でまねられるかどうかさえ、まだ分かっていない。番地が自由に飛ぶと、計算グラフの点に入る辺が多くなりすぎ、グラフを少ない記憶にしまえないからだ、とウィリアムズは説明する。一方、論文の系3.6によると、木の評価が対数の記憶で解ければ $lo g t$ の因子も消え、 $SPACE [t]$ まで下がる。

途中の計算

3つの点の平均と、65,536歩

手順7の等式を、1の3乗根 $ω$ で確かめる。共有の場所に入っていた中身を $x$ 、取り出したい値を $v$ とし、多項式は $P (z) = z^{2}$ とする。

虚数の1の3乗根を $ω$ とおく
$ω = \frac{- 1 + 3 i}{2}, ω^{3} = 1$
$ω^{3} - 1$ を因数分解する
$(ω - 1) (ω^{2} + ω + 1) = 0$
$ω \neq = 1$ なので、和は0になる
$1 + ω + ω^{2} = 0$
3点の値を展開して足す
$i = 1 \sum 3 (ω^{i} x + v)^{2} = x^{2} i = 1 \sum 3 ω^{2 i} + 2 xv i = 1 \sum 3 ω^{i} + 3 v^{2}$
$ω^{2 i}$ も $ω^{2}$ , $ω$ , $1$ と回る
$i = 1 \sum 3 ω^{2 i} = ω^{2} + ω^{4} + ω^{6} = 0$
残った項を3で割る
$\frac{1}{3} i = 1 \sum 3 (ω^{i} x + v)^{2} = v^{2}$

$x$ にどんな値が入っていても、3点で平均をとると消える。多項式を $z^{3}$ にすると、 $ω^{3 i}$ はどれも1なので $x^{3}$ が残り、平均は $x^{3} + v^{3}$ になる。次数が $m$ より小さいという条件は、ここで効いている。ウィリアムズが付録で紹介する形では、この和を標数2の有限体でとる。体の元の数は2の累乗なので $m$ は奇数で、 $m$ 個の和は割らなくてもそのまま $P (v)$ になる。

区切りの長さ $b$ は、証明の手順8にある2つの項の釣り合いで決まる。定数を1とおき、 $lo g$ を2を底にした目安で確かめる。

記憶の目安を書く
$f (b) = b + \frac{t}{b} lo g_{2} b$
$b \leq t$ なので $lo g_{2} b \leq lo g_{2} t$
$f (b) \leq b + \frac{t lo g _{2} t}{b}$
相加平均と相乗平均の関係を使う
$b + \frac{t lo g _{2} t}{b} \geq 2 t lo g_{2} t$
等号が成り立つ $b$ を選ぶ
$b = t lo g_{2} t$
手順8に代入する
$f (t lo g_{2} t) \leq 2 t lo g_{2} t$
$t = 2^{16} = 65, 536$ を入れる
$b = 2^{16} \cdot 16 = 2^{10} = 1, 024$
2つの項を数えて足す
$f (1, 024) = 1, 024 + 64 \times 10 = 1, 664$

t = 2^16のとき、作業領域bは右上がり、メモ（t/b）log₂bは右下がりで、和はbが2^9から2^10のあたりで底になる。

手順9は手順8の右辺の最小値で、 $f$ そのものの最小ではない。当サイトで $f (b)$ を数値で最小にすると、 $b \approx 727$ で $f \approx 1, 584$ になり、手順13の1,664との差は5%ほどだった。同じ $t$ で、1975年の上界 $t / lo g_{2} t$ は4,096、何も工夫しない上界 $t$ は65,536である。

応用

覚える代わりに計算し直す

定理からは、記憶と時間の差が1つ言える。どんな $ε > 0$ を選んでも、記憶 $s$ で解けて $s^{2 - ε}$ の時間では解けない問題がある（論文の系1.2）。たとえば「機械 $M$ は入力 $x$ に対し、記憶 $k$ マスの範囲で止まるか」を問う問題は、多テープチューリング機械では $n^{2 - ε}$ の時間で解けない。線形の記憶で解ける問題に、ほぼ2乗の時間の下限が付いたのである。ウィリアムズは論文の抄録で、PとPSPACEの問題を「少し前に進めた」と表現している。

覚える量と計算し直す手間を釣り合わせる考え方は、計算機の現場でもなじみがある。深層学習の学習では、順伝播で出た途中の値を逆伝播で使うまで覚えておくので、層が $n$ あれば覚える値も $n$ 組になる。

$n$ 層を $k$ 層ずつに区切り、境目の値だけを覚えるとどうなるか。逆伝播で区切りに入るたびに、その区切りの中を順伝播し直して $k$ 組を作る。覚えるのは境目の $n / k$ 組と区切りの中の $k$ 組で、合計 $k + n / k$ は $k = n$ のとき最小の $2 n$ になる。100層なら20組で済み、全部覚える100組の5分の1になる代わりに、計算し直す手間が順伝播1回分ほど増える。

2016年、ティエンチー・チェンらは、 $n$ 層のネットワークを $O (n)$ の記憶で学習させる方法を発表した。1,000層の残差ネットワークでは、記憶を48GBから7GBに減らし、実行時間の増加は30%だったと報告している。ただし、チェンらの方法は区切りを1回ずつ計算し直す素直な工夫で、ウィリアムズの定理を使ったものではない。似ているのは、 $b + (t / b) lo g b$ と $k + n / k$ という釣り合いの形である。

例題と解説

区切りの長さを手で選ぶ

$O$ 記法と多テープチューリング機械は、大学の情報科学で、計算理論や計算量理論の講義に出てくる。例題3と例題4は、複素数の計算だけで解ける。

例題 1基本上界を3つ並べる

$t = 2^{36}$ のとき、何も工夫しない上界 $t$ 、1975年の上界 $t / lo g_{2} t$ 、2025年の上界 $t lo g_{2} t$ を求めよ。定数倍は1とおく。また、1975年の上界は2025年の上界のおよそ何倍か。

解説を見る

$lo g_{2} t = 36$ である。

t = 2^{36} = 68, 719, 476, 736

\frac{t}{lo g _{2} t} = \frac{2 ^{36}}{36} \approx 1, 908, 874, 354

t lo g_{2} t = 2^{36} \cdot 36 = 2^{18} \cdot 6 = 1, 572, 864

比は次のとおり。

\frac{2 ^{36} /36}{2 ^{18} \cdot 6} = \frac{2 ^{18}}{216} \approx 1, 213.6

およそ1,214倍である。

例題 2基本区切りの長さで記憶を比べる

記憶の目安を $f (b) = b + \frac{t}{b} lo g_{2} b$ とし、 $t = 2^{16}$ とする。 $b = 2^{6}$ , $2^{8}$ , $2^{12}$ のそれぞれについて $f (b)$ を求め、いちばん小さいものを答えよ。

解説を見る

$t / b$ はそれぞれ $2^{10}$ , $2^{8}$ , $2^{4}$ である。

f (2^{6}) = 64 + 1, 024 \times 6 = 6, 208

f (2^{8}) = 256 + 256 \times 8 = 2, 304

f (2^{12}) = 4, 096 + 16 \times 12 = 4, 288

いちばん小さいのは $b = 2^{8}$ の2,304である。 $b$ が小さすぎるとメモの項が、大きすぎると作業領域の項がふくらむ。途中の計算で手順13に出た $b = 2^{10}$ は1,664で、さらに小さい。

例題 3入試虚数単位の累乗で平均をとる

$i$ を虚数単位とし、 $x$ , $v$ を複素数とする。

（1） $k = 1 \sum 4 i^{k}$ , $k = 1 \sum 4 i^{2 k}$ , $k = 1 \sum 4 i^{3 k}$ を求めよ。

（2） $k = 1 \sum 4 (i^{k} x + v)^{3} = 4 v^{3}$ を示せ。

解説を見る

（1） $i^{k}$ は $i$ , $- 1$ , $- i$ , $1$ と回る。

k = 1 \sum 4 i^{k} = i - 1 - i + 1 = 0

$i^{2 k}$ は $- 1$ , $1$ , $- 1$ , $1$ 、 $i^{3 k}$ は $- i$ , $- 1$ , $i$ , $1$ と回るので、どちらの和も0である。

（2）二項定理で展開する。

(i^{k} x + v)^{3} = i^{3 k} x^{3} + 3 i^{2 k} x^{2} v + 3 i^{k} x v^{2} + v^{3}

$k = 1$ から4まで足すと、（1）より最初の3つの項は消える。

k = 1 \sum 4 (i^{k} x + v)^{3} = 0 + 0 + 0 + 4 v^{3} = 4 v^{3}

4で割ると $v^{3}$ で、 $x$ によらない。次数3は $m = 4$ より小さい。

例題 4難関次数が足りないと

$ω = \frac{- 1 + 3 i}{2}$ とし、 $x$ , $v$ を複素数とする。

（1） $j = 1 \sum 3 (ω^{j} x + v)^{3}$ を $x$ と $v$ で表せ。

（2）3点での平均 $\frac{1}{3} j = 1 \sum 3 (ω^{j} x + v)^{3}$ が $v^{3}$ に等しくなるのは、 $x$ がどんなときか。

解説を見る

（1）展開すると次のとおり。

j = 1 \sum 3 (ω^{j} x + v)^{3} = x^{3} j \sum ω^{3 j} + 3 x^{2} v j \sum ω^{2 j} + 3 x v^{2} j \sum ω^{j} + 3 v^{3}

$ω^{3 j} = 1$ なので最初の和は3で、残りの2つの和は途中の計算で確かめたとおり0である。

j = 1 \sum 3 (ω^{j} x + v)^{3} = 3 x^{3} + 3 v^{3}

（2）平均は $x^{3} + v^{3}$ なので、 $v^{3}$ に等しいのは $x^{3} = 0$ 、つまり $x = 0$ のときだけである。共有の場所が空でないと、3次の多項式は3点では取り出せない。 $m$ を4以上にする必要がある。

例題 5大学線形の記憶と2乗の時間

空間階層定理「 $s (n) \geq n$ が領域構成可能で $s^{'} (n) = o (s (n))$ なら、 $SPACE [s] \neq \subseteq SPACE [s^{'}]$ 」と本文の定理を使って、 $SPACE [n] \neq \subseteq TIME [n^{1.9}]$ を示せ。

解説を見る

$SPACE [n] \subseteq TIME [n^{1.9}]$ と仮定する。 $t = n^{1.9} \geq n$ に定理を当てはめる。

TIME [n^{1.9}] \subseteq SPACE [n^{1.9} lo g n^{1.9}]

右辺の中身を整理する。

n^{1.9} \cdot 1.9 lo g n = n^{0.95} 1.9 lo g n

$n$ で割ると $1.9 lo g n / n^{0.05}$ で、 $n \to \infty$ で0に近づく。よって $s^{'} (n) = n^{0.95} 1.9 lo g n$ は $o (n)$ である。仮定と合わせると $SPACE [n] \subseteq SPACE [s^{'}]$ となり、 $s (n) = n$ とした空間階層定理に反する。したがって $SPACE [n] \neq \subseteq TIME [n^{1.9}]$ である。1.9を $2 - ε$ に替えても同じ議論が通る。

図示

傾きが半分になった上界

tを横軸、記憶を縦軸にとった両対数のグラフ。何も工夫しないtは傾き1、1975年のt/log tは傾きがほぼ1のままわずかに下にずれ、2025年の√（t log t）は傾きがほぼ1/2になる。

両対数のグラフでは、 $t^{a}$ の形の上界は傾き $a$ の直線になる。1975年の $t / lo g t$ は、 $t$ のすぐ下をほぼ同じ傾きで進み、 $1 0^{12}$ 歩でも $t$ の約40分の1までしか下がらない。2025年の $t lo g t$ は傾きがほぼ半分になり、 $1 0^{12}$ 歩では $t$ の約16万分の1である。

5つの区切りの計算グラフを、最後の区切り5を根とする木に開いた図。同じ区切りが木の何か所にも現れ、深さ優先でたどるときは根から葉までの1本の道だけを覚える。

木に開くと、同じ区切りが何度も現れ、現れるたびに計算し直すので時間は大きく増える。その代わり、覚えるのは、いまいる点から根までの道に置く小さなメモと、使い回す作業領域だけになる。

シミュレーション

作業領域とメモの釣り合い

区切りの長さ $b$ を、 $t$ の何乗かで動かす。「足して戻す」では、区切り1つ分の作業領域 $b$ と、段ごとの小さなメモ $(t / b) lo g_{2} b$ の和が記憶になり、グラフの谷が最も少ない $b$ を示す。「そのまま覚える」に切り替えると、段ごとに区切り1つ分を覚えるので、 $b$ をどう選んでも記憶は $t$ のまま動かない。値は定数を1とおき、計算グラフの印の分を省いた目安で、100万歩では谷の底が約6,840と、 $t lo g_{2} t \approx 4, 464$ の約1.5倍になる。

広がる学問

回路、多項式、学習の記憶

情報科学 同じ問題の難しさを、時間で測るか記憶で測るかで比べるときに使う。どんな $ε > 0$ でも $TIME [t] \subseteq SPACE [t^{ε}]$ まで縮められればPとPSPACEが異なることになる、とウィリアムズは指摘している。大きさ $s$ の回路の出力を、どの入力でもおよそ $s$ の記憶で求められることも導かれる。
数学多項式の値や係数を、1の $m$ 乗根について和をとって取り出すときに使う。 $\sum_{i = 1}^{m} ω^{ik}$ は $k$ が $m$ の倍数なら $m$ 、それ以外は0になるので、次数が $m$ より小さい多項式では、平均をとると定数の項だけが残る。オイラーの公式で $ω = e^{2 π i / m}$ と書けば、離散フーリエ変換も同じ性質の上に立っている。
工学深層学習の学習や自動微分で、途中の値を覚える量と計算し直す手間を釣り合わせるときに使う。1992年、アンドレアス・グリーヴァンクは、逆向きの自動微分で、時間と記憶の増え方をどちらも対数の倍率に抑えられることを示した。 $n$ 層を $n$ 層ずつに区切る学習の方法も、同じ計算し直しの考え方に立つ。

いまの研究と事業

木の評価はどこまで縮むか

2024年オデッド・ゴールドライヒ（ワイツマン科学研究所）: 値のビット数を $ℓ$ 、木の高さを $h$ とすると、クックとマーツの手順の記憶は $O (ℓ + h lo g ℓ)$ で、 $O ((h + ℓ) lo g (h + ℓ))$ を超えない。ゴールドライヒはこれを $lo g lo g (h + ℓ)$ の因子だけ下回る、 $o ((h + ℓ) lo g (h + ℓ))$ の記憶で解いた。 $d$ 分木に広げた手順を改良し、二分木を $d$ 分木に組み直して高さを $lo g_{2} d$ 分の1にする。主な結果はダートマス大学の学生が半年前に得ていた、とゴールドライヒは断っている。木の評価が対数の記憶 $O (h + ℓ)$ に届けば、証明の手順8の $lo g b$ が消え、 $TIME [t] \subseteq SPACE [t]$ になる。出典はECCC TR24-124。
2025年ヤコフ・シャルノフ（シカゴ大学）: チューリング機械を経ずに、回路の値を求める問題を木の評価に直接帰着させた。大きさ $s$ の回路の出力を、どの入力についても $O (s lo g s)$ の記憶で求められる。ウィリアムズの定理から出る $O (s polylog s)$ を改良し、逆に $t$ 歩の計算を $O (t lo g t)$ の記憶でシミュレートする、少し弱い形の定理も導ける。出典は2025年4月に公開された原稿arXiv:2504.20950。
2024〜2025年クック、マーツら4人: 対数の記憶に、元へ戻す約束で借りた記憶を足して解ける問題のクラスをCLと呼ぶ。4人は、ここに乱数を加えても解ける問題が増えないこと、つまりCBPL = CLを、仮定なしに示した。証明の手順7で $x^+ v + v = x^$ として借りた場所を元へ戻したように、使い終えた記憶を元どおりにするのが触媒計算の約束である。論文は2024年6月にECCCで公開され、STOC 2025に載った。出典はECCC TR24-106。
2022年NVIDIAの研究者7人: 大規模なTransformerの学習で、途中の値を層ごとに全部計算し直す代わりに、注意機構のうち、記憶を多く使うわりに計算の軽い部分だけを選んで計算し直す方法を提案した。系列並列と組み合わせて、途中の値を覚える記憶を5分の1にし、計算し直しにかかる余分な時間を90%以上減らしている。5,300億パラメーターのモデルを2,240基のA100で学習させた例では、全部を計算し直す方法より29%速かった。覚える量 $k$ と計算し直す量 $n / k$ の釣り合いを、部分ごとに選び直す形である。出典はarXiv:2205.05198。

参考文献

R. Williams, "Simulating Time with Square-Root Space", STOC 2025, 13-23（ECCC TR25-017, 2025年2月24日; arXiv:2502.17779）; J. ACM 73(3) (2026), 1-25.
J. Hopcroft, W. Paul, L. Valiant, "On time versus space and related problems", FOCS 1975, 57-64; "On Time Versus Space", J. ACM 24(2) (1977), 332-337; J. E. Hopcroft, J. D. Ullman, "Relations Between Time and Tape Complexities", J. ACM 15(3) (1968), 414-427; W. J. Paul, R. E. Tarjan, J. R. Celoni, "Space bounds for a game on graphs", Mathematical Systems Theory 10 (1976), 239-251.
J. Cook, I. Mertz, "Tree Evaluation Is in Space O(log n · log log n)", STOC 2024, 1268-1278（ECCC TR23-174）; SIAM J. Comput. (2025); S. Cook, P. McKenzie, D. Wehr, M. Braverman, R. Santhanam, "Pebbles and Branching Programs for Tree Evaluation", ACM Trans. Comput. Theory 3(2) (2012); H. Buhrman, R. Cleve, M. Koucký, B. Loff, F. Speelman, "Computing with a full memory", STOC 2014, 857-866.
O. Goldreich, "Solving Tree Evaluation in o(log n · log log n) space", ECCC TR24-124 (2024); Y. Shalunov, "Improved Bounds on the Space Complexity of Circuit Evaluation", arXiv:2504.20950 (2025); J. Cook, J. Li, I. Mertz, E. Pyne, "The Structure of Catalytic Space: Capturing Randomness and Time via Compression", STOC 2025, 554-564（ECCC TR24-106）.
T. Chen, B. Xu, C. Zhang, C. Guestrin, "Training Deep Nets with Sublinear Memory Cost", arXiv:1604.06174 (2016); A. Griewank, "Achieving logarithmic growth of temporal and spatial complexity in reverse automatic differentiation", Optimization Methods and Software 1(1) (1992), 35-54; V. Korthikanti et al., "Reducing Activation Recomputation in Large Transformer Models", arXiv:2205.05198 (2022).
ACM SIGACT, "STOC Best Paper Award"（STOC 2025の受賞論文）; Cornell Bowers CIS, "Time, Space, and the Mysteries of Efficient Computation"（Computer Science Colloquium、2025年10月9日）; R. Williams, Curriculum Vitae (MIT CSAIL).

t歩の計算は、ほぼ√tの記憶で足りる（ウィリアムズの定理）

0.99乗でも足りないはずだった

1975年の小石と、2023年の木

借りた記憶でたどる区切りの木

3つの点の平均と、65,536歩

覚える代わりに計算し直す

区切りの長さを手で選ぶ

例題 1基本上界を3つ並べる

例題 2基本区切りの長さで記憶を比べる

例題 3入試虚数単位の累乗で平均をとる

例題 4難関次数が足りないと

例題 5大学線形の記憶と2乗の時間

傾きが半分になった上界

作業領域とメモの釣り合い

回路、多項式、学習の記憶

木の評価はどこまで縮むか

参考文献

タグ

同じタグを持つ公式

姉妹サイト