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

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

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

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

MIT 的理論計算機科學家 Ryan Williams 的最新研究建立了一種數學程序，能夠將任意算法 —— 無論其具體執行何種任務 —— 轉化為一種占用空間顯著更少的形式， 證明少量計算內存（空間）在理論上比大量計算時間更有價值，這顛覆了計算機科學家近 50 年來的認知。 

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

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

50 年的探索與瓶頸 

Juris Hartmanis

1965 年， Juris Hartmanis 和 Richard Stearns 兩人合作發表了兩篇開創性論文，首次對「時間」（Time）和「空間」（Space）這兩個概念建立了嚴格的數學定義。

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

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

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

這兩個類別之間的關系是復雜性理論中的核心問題之一。

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

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

然而，復雜性理論家不滿足于這種直覺推理：他們需要嚴謹的數學證明。要證明 PSPACE 類確實嚴格大于 P 類，研究人員必須能夠展示存在某些 PSPACE 內的問題，其本質上不可能被快速算法求解。

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

然而，隨后研究進展停滯，復雜性理論學者開始懷疑，他們或許已經碰到了一個根本性的障礙。

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

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

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

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

打破僵局

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

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

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

此后超過十年的時間里，復雜性理論研究者一直在嘗試彌合這一漏洞。直到 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 步內的計算問題 —— 特別是判斷其最終狀態或輸出 —— 規約 (reduce) 成一個「樹評估問題」 (Tree Evaluation Problem, TEP) 的實例。

這個構造出來的樹評估問題實例具有特定的參數：樹的高度 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)。