作者：Ben Brubaker
機器之心編譯
相信大家都有過這樣的經驗：執行某個程式時，電腦突然卡住，輕則恢復檔案，重則重新建立；或是手機頻繁跳出「記憶體不足」的警告，讓我們不得不忍痛刪除珍貴的照片或應用程式。
這些日常的煩惱，其實都指向了計算世界中兩個至關重要的基本要素：時間和空間。
時間和空間（也稱為記憶體）是計算中最基本的兩種資源：任何演算法在執行時都需要一定的時間，並在執行過程中佔用一定的空間以儲存資料。
以往已知的某些任務的演算法，其所需的空間大致與執行時間成正比，研究人員長期以來普遍認為這一點無法改進。
麻省理工學院的理論電腦科學家 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)。
參考連結：
https://www.quantamagazine.org/for-algorithms-a-little-memory-outweighs-a-lot-of-time-20250521/
https://arxiv.org/pdf/2502.17779
© THE END
轉載請聯繫本公眾號獲得授權
投稿或尋求報導：liyazhou@jiqizhixin.com