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

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

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

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

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

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

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

50 年的探索與瓶頸 

Juris Hartmanis

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

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

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

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

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

所有屬于 P 類的問(wèn)題也都屬于 PSPACE 類，這是因?yàn)榭焖偎惴ㄔ谶\(yùn)行時(shí)通常沒(méi)有足夠的時(shí)間使用大量計(jì)算機(jī)內(nèi)存空間。反之亦然，即所有 PSPACE 類問(wèn)題也都能通過(guò)快速算法求解，則兩個(gè)類別將完全等價(jià)：計(jì)算時(shí)間與計(jì)算空間在能力上將無(wú)本質(zhì)差異。

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

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

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

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

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

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

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

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

打破僵局

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

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

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

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

Cook（左） 與 Mertz（右）

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

Williams 的革命性飛躍

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

Ryan Williams

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

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

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

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

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

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

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

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

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

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

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

代入 Cook-Mertz 算法的空間復(fù)雜度公式（特別是 d^(h/2) 這一項(xiàng)），并綜合其他因素（如 log t 因子，來(lái)源于對(duì)指針、計(jì)數(shù)器等的記錄），最終推導(dǎo)出總的模擬空間復(fù)雜度為 O (√t log t)。