白交 發自 凹非寺
量子位 | 公眾號 QbitAI

一個計算機領域的著名問題，在停滯50年之后終于有了進展。

MIT科學家威廉姆斯一次偶然發現：證明內存比大家認為的更強大。在所有可以想象的計算中，少量的內存與大量的時間一樣有價值

時間和內存（空間）是計算中最基本的兩種資源，每個算法都需要一些時間來運行，并且在運行時需要一些空間來存儲數據。迄今為止，已知的算法里所需的空間與其運行時間基本上都成正比，研究人員認為沒有更好的辦法。

但現在威廉姆斯證明，存在一個數學程序，可以將任何算法轉換成「占用更少空間」的形式。

由于想法過于不可思議，他當時第一想法是：大概是自己瘋了吧

于是開始著手證明自己錯了，但想了幾個小時也沒找出任何瑕疵：沒準萬一真就自己對了呢。

經過幾個月的整理和推敲，最終將成果po到網上，沒想到收獲大家一種好評。

一華盛頓大學科學家表示：這是一個相當驚人的結果，也是一個巨大的進步

困擾計算機科學家的半世紀難題

先來看看這是一個什么問題。

如果用大白話來講，這個問題其實源于我們一種直覺：你可以重復使用空間，但不能重復使用時間

算法可以反復使用同一小塊內存，而時間卻不那么寬容，一旦過去，就無法再收回。

但對于正經科學家來說，直覺是不夠的，這需要嚴謹的證明！

哎，這就難到科學家了，沒成想一難就難了半世紀。（Doge）

威廉姆斯所在的領域是計算機科學一個分支學科計算復雜性理論

這個領域就是解決諸如列表排序或因式分解等計算問題所需的資源（例如時間和空間）。大多數問題可以通過多種不同的算法來解決，每種算法對時間和空間都有各自的需求。復雜性理論家根據最佳算法（即運行速度最快或占用空間最少的算法）的資源需求，將問題劃分為不同的類別，稱為復雜性類別。

但是，如何讓計算資源的研究實現數學上的嚴謹程度呢？如果只是單純地分析時間和空間，那是不可能的。要想取得進展，首先需要正確的定義。

20世紀60年代，計算機科學家哈特馬尼斯建立了用來分析時間和空間的精確定義——

P，涵蓋了所有可以在合理時間內解決的問題。空間領域的一個類似復雜性類別被稱為“PSPACE”

這兩類問題之間的關系是復雜性理論的核心問題之一。P 中的所有問題也都屬于 PSPACE 問題，因為快速算法根本沒有足夠的時間填滿計算機內存中的大量空間。

如果反過來也成立，那么這兩個類將是等價的：空間和時間將具有相當的計算能力

但科學家們懷疑 PSPACE 是一個更大的類，包含許多 P 中沒有的問題。換句話說，他們認為空間是一種比時間更強大的計算資源

為了證明PSPACE大于P，研究人員必須證明，對于PSPACE中的某些問題，快速算法絕對不可能實現。

1965年，哈特馬尼斯搬到了康奈爾大學，擔任新成立的計算機科學系主任。在他的領導下，該系迅速發展成為復雜性理論的研究中心。

20世紀70年代初，那里的兩位研究人員約翰·霍普克羅夫特和沃爾夫岡·保羅著手建立時間和空間之間的精確聯系。

他們知道，要解決 P 與 PSPACE 的問題，就必須證明在有限的時間內無法完成某些計算。但要證明這一點卻很難。

因此，他們決定反過來思考這個問題，探索有限空間下能做什么。他們希望證明，給定一定空間預算的算法可以解決與時間預算稍長的算法相同的所有問題。這表明空間至少比時間略勝一籌——這是證明 PSPACE 大于 P 的一個小而必要的步驟。

為了實現這一目標，他們轉向了一種“模擬”方法，即將現有算法轉化為解決相同問題的新算法，但所需的空間和時間有所不同。

有個通俗的例子，你得到了一個快速算法，可以按字母順序排列書架，但它需要你把書堆成幾十個小堆。你可能更喜歡一種占用公寓空間更少的方法，即使它需要更長的時間。

模擬是一種數學過程，你可以用來得到更合適的算法：輸入原始算法，它會給出一個新的算法，以節省空間但犧牲時間。

他們倆想要開發一種通用的模擬程序，可以適用于所有算法，哪怕只是節省一點點空間。時間來到1975年， 在一個年輕研究員瓦利安特參與下，他們仨終于把這個想法實現了。

△瓦利安特

但隨后進展停滯，復雜性理論家開始懷疑他們遇到了一個根本性的障礙。問題恰恰在于模擬的普適性和通用性。

• 雖然許多問題可以用比時間少得多的空間來解決，但有些問題直觀上似乎需要幾乎與時間一樣多的空間。

而且當時的作者保羅Paul與合著者也很快證明確實不可能實現普適性

于是這個問題就這樣持續了50年都沒有解決。

威廉姆斯是怎么解決的？

1996年，他來到了康奈爾大學，追隨哈特馬尼斯的腳步。

他自從大學第一次遇到這個問題以來就一直著迷，他甚至在計算機科學課程之外還學習了邏輯學和哲學課程，試圖從其他時間和空間視角中尋找靈感，但最終卻徒勞無功。

一次轉機是在2010年另一個關于計算記憶問題的進展：哪些問題可以用極其有限的空間來解決？

2010 年，復雜性理論先驅 Stephen Cook 和他的同事發明了一項名為“樹評估問題”的任務。他們證明了，任何空間預算低于特定閾值的算法都不可能實現這一點。但這其中存在一個bug。該證明依賴于保羅和他的同事幾十年前提出的一個常識性假設：算法無法將新數據存儲在已滿的空間中

十多年來，科學家們一直試圖彌補這一bug。結果在2023年，Cook的兒子和他的工作伙伴，設計了個算法解決了樹評估問題，結果發現占用的空間比任何人想象的都要少得多。

老Cook將數據比做鵝卵石，無法擠壓，必須在算法的內存中占據不同的位置。但事實證明，這并非存儲數據的唯一方式，可以將這些鵝卵石想象成可以稍微擠壓在一起的東西。

威廉姆斯在一堂課上靈光乍現：

• 誒那既然數據可以擠壓，這是不是這個方法就相當于是個可以減少空間內存的通用工具了！

經過進一步研究發現，這種模擬可以讓新算法的空間占用大大減少——大約等于原始算法時間預算的平方根

這種新的節省空間的算法也會慢得多，因此該模擬不太可能有實際應用。但從理論角度來看，這無疑是革命性的。

然后，他僅用幾行數學運算，就反過來證明了時間計算能力的一個消極結果：至少有一些問題除非使用的時間多于空間，否則無法解決。第二個范圍更窄的結果與研究人員的預期一致。

從定性角度來看，威廉姆斯的第二個結果聽起來像是人們長期尋求的P與PSPACE問題的解決方案。

兩者的區別在于規模。

P和PSPACE是非常廣泛的復雜性類別，而威廉姆斯的結果則在更精細的層面上進行。

不要要證明PSPACE大于P，研究人員必須進一步擴大這一差距。但威廉姆斯花了幾個月的時間嘗試擴展都失敗了。

半世紀前參與通用模擬的那個年輕研究員瓦利安特，目前他在哈佛大學任教，他表示

• 這可能是一個終極瓶頸，也可能是一個持續50年的瓶頸。
• 又或者下周就可能解決。

大二老師曾勸他轉方向

不過現在看46歲的他取得了很大的進展，但幾十年前也曾被老師轉方向。

威廉姆斯童年住在阿拉巴馬州鄉村，那里有一個50英畝大的農場。

7歲時第一次見到電腦，當時他的母親開車帶他穿過縣城去參加一個特殊的學術強化班。他回憶說，當時一個用于生成數字煙花表演的簡單程序讓他著迷——

隨機選取一種顏色，然后從顯示器中央向隨機方向發送。「你永遠無法預測最終會得到一個什么樣的圖像」。

這正是那時候開始，他就產生了濃厚的興趣，沒有計算機那就在紙上寫程序，父母也不知道拿他怎么辦。

高中最后兩年，他轉學到阿拉巴馬數學與科學學校，在那里他第一次接觸到計算機科學的理論知識，也第一次確定了想做的事情：

• 我意識到外面的世界更加廣闊，而且有辦法用數學的方式思考計算機

而到了申請大學的時候，他知道攻讀復雜性理論需要遠離家鄉，但他的父母明確表示，西海岸和加拿大是不可能的。在剩下的選擇中，康奈爾大學脫穎而出。

于是他憑借豐厚的經濟資助，來到了這個夢中情地，這個理論的起始之地康奈爾大學

不過到了大二，他就很難跟上課程了。他在一門計算理論課上只得到了中等成績，老師建議他考慮其他職業。

但他不肯，決定加倍努力，修了一門研究生理論課，希望在這門難度更大的課上取得優異的成績，能讓他研究生申請時顯得格外突出。

而教授這門研究生課程的教授正是哈特馬尼斯，彼時他已是該領域的元老級人物。

威廉姆斯開始每周參加哈特馬尼斯的辦公室課程，幾乎總是唯一到場的學生。他的堅持得到了回報：他在課程中獲得了A，哈特馬尼斯也同意在下個學期指導他完成一個獨立研究項目。

大學期間，他們兩個一直保持著每周的會面。哈特馬尼斯鼓勵他培養一種個性化的復雜性研究方法，并引導他避開死胡同。

在這之后他始終在研究復雜性理論。2010年，他證明了一個里程碑式成果，被認為是朝著P與NP問題解決邁進。

這一成果鞏固了威廉姆斯的聲譽，他隨后又撰寫了數十篇關于復雜性理論不同主題的論文。

不過，P 對 PSPACE 這個問題一直在他腦海中揮之不去：我只是想不出什么足夠有趣的東西。

這就是真·念念不忘，必有回響吧。

https://www.quantamagazine.org/for-algorithms-a-little-memory-outweighs-a-lot-of-time-20250521/