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

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

1965年，哈特馬尼斯搬到了康奈爾大學(xué)，擔(dān)任新成立的計算機科學(xué)系主任。在他的領(lǐng)導(dǎo)下，該系迅速發(fā)展成為復(fù)雜性理論的研究中心。

20世紀(jì)70年代初，那里的兩位研究人員約翰·霍普克羅夫特和沃爾夫?qū)けＡ_著手建立時間和空間之間的精確聯(lián)系。

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

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

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

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

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

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

△瓦利安特

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

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

而且當(dāng)時的作者保羅Paul與合著者也很快證明確實不可能實現(xiàn)普適性。

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

威廉姆斯是怎么解決的？

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

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

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

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

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

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

威廉姆斯在一堂課上靈光乍現(xiàn)：

誒那既然數(shù)據(jù)可以擠壓，這是不是這個方法就相當(dāng)于是個可以減少空間內(nèi)存的通用工具了！

經(jīng)過進一步研究發(fā)現(xiàn)，這種模擬可以讓新算法的空間占用大大減少——大約等于原始算法時間預(yù)算的平方根。

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

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

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

兩者的區(qū)別在于規(guī)模。

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

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

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

這可能是一個終極瓶頸，也可能是一個持續(xù)50年的瓶頸。

又或者下周就可能解決。

大二老師曾勸他轉(zhuǎn)方向

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

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

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

隨機選取一種顏色，然后從顯示器中央向隨機方向發(fā)送?！改阌肋h(yuǎn)無法預(yù)測最終會得到一個什么樣的圖像」。

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

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

我意識到外面的世界更加廣闊，而且有辦法用數(shù)學(xué)的方式思考計算機。

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

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

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

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

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

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

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

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

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

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

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

參考鏈接：
https://www.quantamagazine.org/for-algorithms-a-little-memory-outweighs-a-lot-of-time-20250521/