選自量子雜志

作者：Ben Brubaker

機器之心編譯

相信大家都曾有過這樣的經(jīng)歷：運行某個程序時，電腦突然卡住，輕則恢復(fù)文件，重則重新創(chuàng)建；或者手機頻繁彈出「內(nèi)存不足」的警告，讓我們不得不忍痛刪除珍貴的照片或應(yīng)用。

這些日常的煩惱，其實都指向了計算世界中兩個至關(guān)重要的基本要素：時間和空間。

時間和空間（也稱為內(nèi)存）是計算中最基本的兩種資源：任何算法在執(zhí)行時都需要一定的時間，并在運行過程中占用一定的空間以存儲數(shù)據(jù)。

以往已知的某些任務(wù)的算法，其所需的空間大致與運行時間成正比，研究人員長期以來普遍認(rèn)為這一點無法改進(jìn)。

MIT 的理論計算機科學(xué)家 Ryan Williams 的最新研究建立了一種數(shù)學(xué)程序，能夠?qū)⑷我馑惴?—— 無論其具體執(zhí)行何種任務(wù) —— 轉(zhuǎn)化為一種占用空間顯著更少的形式，證明少量計算內(nèi)存（空間）在理論上比大量計算時間更有價值，這顛覆了計算機科學(xué)家近 50 年來的認(rèn)知。

• 論文標(biāo)題： Simulating Time With Square-Root Space
• 論文地址：https://arxiv.org/pdf/2502.17779

更重要的是，這一結(jié)果不僅揭示了在特定空間約束下可執(zhí)行的計算范圍，還間接證明了在有限時間內(nèi)無法完成的計算類型。雖然后者早已預(yù)期它成立，但一直缺乏嚴(yán)格的證明方法。

50 年的探索與瓶頸

Juris Hartmanis

1965 年， Juris Hartmanis 和 Richard Stearns 兩人合作發(fā)表了兩篇開創(chuàng)性論文，首次對「時間」（Time）和「空間」（Space）這兩個概念建立了嚴(yán)格的數(shù)學(xué)定義。

• 論文地址：https://doi.org/10.1090/S0002-9947-1965-0170805-7

這些定義為研究人員提供了一種共同的語言，使他們能夠比較這兩類資源，并據(jù)此將問題劃分為不同的復(fù)雜性類別（complexity classes）。

其中一個最重要的復(fù)雜性類別 P 類，粗略地說，P 類包含所有能夠在合理時間內(nèi)求解的問題。與之對應(yīng)的一個空間復(fù)雜度類別被稱為 PSPACE 類 。

這兩個類別之間的關(guān)系是復(fù)雜性理論中的核心問題之一。

所有屬于 P 類的問題也都屬于 PSPACE 類，這是因為快速算法在運行時通常沒有足夠的時間使用大量計算機內(nèi)存空間。反之亦然，即所有 PSPACE 類問題也都能通過快速算法求解，則兩個類別將完全等價：計算時間與計算空間在能力上將無本質(zhì)差異。

然而，復(fù)雜性理論研究者普遍認(rèn)為，PSPACE 類的規(guī)模要大得多，其中包含許多不屬于 P 類的問題。換言之，他們相信，從計算能力角度來看，空間是一種遠(yuǎn)比時間更為強大的資源。這種信念源于這樣一個事實：算法可以反復(fù)使用同一小塊內(nèi)存，而時間卻無法重復(fù)利用 —— 一旦過去，就無法重來。

然而，復(fù)雜性理論家不滿足于這種直覺推理：他們需要嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)證明。要證明 PSPACE 類確實嚴(yán)格大于 P 類，研究人員必須能夠展示存在某些 PSPACE 內(nèi)的問題，其本質(zhì)上不可能被快速算法求解。

1975 年，John Hopcroft、Wolfgang Paul 和 Leslie Valiant 設(shè)計了一個通用的「模擬程序」，證明了任何在特定時間內(nèi)完成的任務(wù)，都可以在略少于該時間的空間內(nèi)完成。這是連接時間和空間的第一個重要步驟，表明空間至少比時間略強。

然而，隨后研究進(jìn)展停滯，復(fù)雜性理論學(xué)者開始懷疑，他們或許已經(jīng)碰到了一個根本性的障礙。

問題正出在 Hopcroft、Paul 和 Valiant 所提出的模擬方法的「通用性」特征上。雖然許多問題確實可以在遠(yuǎn)小于其時間預(yù)算的空間內(nèi)求解，但一些問題從直覺上來看，似乎需要幾乎與時間等量的空間。如果這種情況確實存在，那么更高效地節(jié)省空間的通用模擬將無從談起。

不久之后，Paul 與另外兩位研究者一道證明了這一點：更高效的通用模擬確實是不可能的，只要采納一個看似理所當(dāng)然的前提 ——不同的數(shù)據(jù)塊在任何時刻不能同時占用同一塊內(nèi)存空間。

Paul 的研究結(jié)果表明，若要真正解決 P 與 PSPACE 的關(guān)系問題（P versus PSPACE problem），就必須徹底放棄以模擬（simulation）為中心的研究路徑，轉(zhuǎn)而尋找一種全新的理論方法。問題在于，當(dāng)時沒人能提出可行的替代方案。

這個研究難題因此陷入僵局，整整持續(xù)了五十年 —— 直到 Williams 的工作最終打破了這一僵持局面。

打破僵局

Williams 的新研究源于對另一個計算中內(nèi)存使用問題的突破性進(jìn)展：哪些問題可以在極其有限的空間下被解決？

2010 年，復(fù)雜性理論先驅(qū) Stephen Cook 與他的合作者設(shè)計出一道被稱為樹評估問題（tree evaluation problem）的新任務(wù)，并證明：任何算法若受制于低于某一特定閾值的空間預(yù)算，都無法解決這個問題。

然而，這項證明中存在一個漏洞。其推理依賴于 Paul 等人數(shù)十年前提出的直覺性假設(shè)：算法不能將新數(shù)據(jù)存入已經(jīng)被占用的內(nèi)存空間。

此后超過十年的時間里，復(fù)雜性理論研究者一直在嘗試彌合這一漏洞。直到 2023 年，Stephen Cook 的兒子 James Cook 與研究者 Ian Mertz 推翻了這一假設(shè)。他們設(shè)計出一種全新的算法，能夠以遠(yuǎn)低于此前認(rèn)為的空間開銷，解決樹評估問題。這一結(jié)果使得原有下界證明完全失效。

Cook（左） 與 Mertz（右）

原先 Stephen Cook 的證明假設(shè)中，信息位（bit）被視作類似「石子」（pebbles），必須被存放在算法內(nèi)存中的不同位置。而事實證明，數(shù)據(jù)的存儲方式遠(yuǎn)比這更為靈活。

Williams 的革命性飛躍

Cook 與 Mertz 提出的算法引起了眾多研究者的興趣，但起初尚不清楚它是否適用于樹評估問題（tree evaluation problem）之外的其他場景。

Ryan Williams

2024 年春季，Ryan Williams 任教的一門課中，一組學(xué)生將 Cook 和 Mertz 的論文作為期末項目進(jìn)行展示。學(xué)生們的熱情激發(fā)了他的興趣，使他決定深入研究這項工作。

一旦著手，他便迅速捕捉到一個關(guān)鍵想法：他意識到，Cook 與 Mertz 提出的方法實質(zhì)上是一個通用的空間壓縮工具。他想到：為何不利用這一工具，設(shè)計一種全新的通用模擬機制（universal simulation），以更優(yōu)的形式鏈接時間與空間復(fù)雜度？就像當(dāng)年 Hopcroft、Paul 和 Valiant 所構(gòu)筑的模型，只不過性能更強。

那項經(jīng)典成果提供了一種方式，可以將任意具有給定時間預(yù)算（time budget）的算法，轉(zhuǎn)化為一個空間預(yù)算略小的新算法。Williams 則認(rèn)識到，倘若基于「柔性石子」（squishy pebbles）建立模擬技術(shù)，轉(zhuǎn)化后的新算法所需空間將更大幅度降低 —— 大致等于最初時間預(yù)算的平方根。

這種新型節(jié)省空間的算法運算速度會顯著下降，因此不太可能有實際應(yīng)用。但從理論角度來看，其意義堪稱革命性突破。

Williams 的模擬方法從一個已有的概念 ——「塊規(guī)整圖靈機模擬」 (block-respecting Turing machine simulation) 出發(fā)并進(jìn)行了推廣。其基本思路是將整個計算過程（假設(shè)總共 t 個計算步驟）分解為 t/b 個連續(xù)的「計算塊」(computation blocks)，每個塊包含 b 個計算步驟。

這些「計算塊」的輸入 / 輸出狀態(tài)（或稱為「配置」）之間存在依賴關(guān)系，可以形成一個「計算圖」 (computation graph)。

Williams 的關(guān)鍵步驟是將這個圖靈機在 t 步內(nèi)的計算問題 —— 特別是判斷其最終狀態(tài)或輸出 —— 規(guī)約 (reduce) 成一個「樹評估問題」 (Tree Evaluation Problem, TEP) 的實例。

這個構(gòu)造出來的樹評估問題實例具有特定的參數(shù)：樹的高度 h 大致為 t/b（即計算塊的數(shù)量），每個節(jié)點傳遞的信息的位長度為 b，樹的扇入度（每個節(jié)點有多少子節(jié)點）為 d（一個取決于圖靈機本身的小常數(shù)）。

重要的是，這棵「樹」是「隱式定義」的，意味著不需要在內(nèi)存中實際構(gòu)建出整棵樹，而是有一套規(guī)則可以隨時確定樹的任何部分應(yīng)該是什么樣子。

對于這個構(gòu)造出來的「樹評估問題」實例，Williams 應(yīng)用了由 Cook 和 Mertz 提出的算法來求解，Cook-Mertz 算法解決這類樹評估問題的空間復(fù)雜度大致是 d^(h/2) * poly (b, h) （其中 d 是扇入度，h 是樹高，b 是位長）。

Williams 接著分析了總的空間復(fù)雜度，并通過精心選擇「計算塊」的大小 b 來進(jìn)行優(yōu)化。當(dāng)參數(shù) b 被設(shè)定為大約 √t (總計算時間 t 的平方根) 時，前面提到的樹高 h (約為 t/b) 就變成了大約 √t。

代入 Cook-Mertz 算法的空間復(fù)雜度公式（特別是 d^(h/2) 這一項），并綜合其他因素（如 log t 因子，來源于對指針、計數(shù)器等的記錄），最終推導(dǎo)出總的模擬空間復(fù)雜度為 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