白交 發(fā)自 凹非寺
量子位 | 公眾號(hào) QbitAI

一個(gè)計(jì)算機(jī)領(lǐng)域的著名問(wèn)題，在停滯50年之后終于有了進(jìn)展。

MIT科學(xué)家威廉姆斯一次偶然發(fā)現(xiàn)：證明內(nèi)存比大家認(rèn)為的更強(qiáng)大。在所有可以想象的計(jì)算中，少量的內(nèi)存與大量的時(shí)間一樣有價(jià)值

時(shí)間和內(nèi)存（空間）是計(jì)算中最基本的兩種資源，每個(gè)算法都需要一些時(shí)間來(lái)運(yùn)行，并且在運(yùn)行時(shí)需要一些空間來(lái)存儲(chǔ)數(shù)據(jù)。迄今為止，已知的算法里所需的空間與其運(yùn)行時(shí)間基本上都成正比，研究人員認(rèn)為沒(méi)有更好的辦法。

但現(xiàn)在威廉姆斯證明，存在一個(gè)數(shù)學(xué)程序，可以將任何算法轉(zhuǎn)換成「占用更少空間」的形式。

由于想法過(guò)于不可思議，他當(dāng)時(shí)第一想法是：大概是自己瘋了吧

于是開(kāi)始著手證明自己錯(cuò)了，但想了幾個(gè)小時(shí)也沒(méi)找出任何瑕疵：沒(méi)準(zhǔn)萬(wàn)一真就自己對(duì)了呢。

經(jīng)過(guò)幾個(gè)月的整理和推敲，最終將成果po到網(wǎng)上，沒(méi)想到收獲大家一種好評(píng)。

一華盛頓大學(xué)科學(xué)家表示：這是一個(gè)相當(dāng)驚人的結(jié)果，也是一個(gè)巨大的進(jìn)步

困擾計(jì)算機(jī)科學(xué)家的半世紀(jì)難題

先來(lái)看看這是一個(gè)什么問(wèn)題。

如果用大白話來(lái)講，這個(gè)問(wèn)題其實(shí)源于我們一種直覺(jué)：你可以重復(fù)使用空間，但不能重復(fù)使用時(shí)間

算法可以反復(fù)使用同一小塊內(nèi)存，而時(shí)間卻不那么寬容，一旦過(guò)去，就無(wú)法再收回。

但對(duì)于正經(jīng)科學(xué)家來(lái)說(shuō)，直覺(jué)是不夠的，這需要嚴(yán)謹(jǐn)?shù)淖C明！

哎，這就難到科學(xué)家了，沒(méi)成想一難就難了半世紀(jì)。（Doge）

威廉姆斯所在的領(lǐng)域是計(jì)算機(jī)科學(xué)一個(gè)分支學(xué)科計(jì)算復(fù)雜性理論

這個(gè)領(lǐng)域就是解決諸如列表排序或因式分解等計(jì)算問(wèn)題所需的資源（例如時(shí)間和空間）。大多數(shù)問(wèn)題可以通過(guò)多種不同的算法來(lái)解決，每種算法對(duì)時(shí)間和空間都有各自的需求。復(fù)雜性理論家根據(jù)最佳算法（即運(yùn)行速度最快或占用空間最少的算法）的資源需求，將問(wèn)題劃分為不同的類別，稱為復(fù)雜性類別。

但是，如何讓計(jì)算資源的研究實(shí)現(xiàn)數(shù)學(xué)上的嚴(yán)謹(jǐn)程度呢？如果只是單純地分析時(shí)間和空間，那是不可能的。要想取得進(jìn)展，首先需要正確的定義。

20世紀(jì)60年代，計(jì)算機(jī)科學(xué)家哈特馬尼斯建立了用來(lái)分析時(shí)間和空間的精確定義——

P，涵蓋了所有可以在合理時(shí)間內(nèi)解決的問(wèn)題。空間領(lǐng)域的一個(gè)類似復(fù)雜性類別被稱為“PSPACE”

這兩類問(wèn)題之間的關(guān)系是復(fù)雜性理論的核心問(wèn)題之一。P 中的所有問(wèn)題也都屬于 PSPACE 問(wèn)題，因?yàn)榭焖偎惴ǜ緵](méi)有足夠的時(shí)間填滿計(jì)算機(jī)內(nèi)存中的大量空間。

如果反過(guò)來(lái)也成立，那么這兩個(gè)類將是等價(jià)的：空間和時(shí)間將具有相當(dāng)?shù)挠?jì)算能力

但科學(xué)家們懷疑 PSPACE 是一個(gè)更大的類，包含許多 P 中沒(méi)有的問(wèn)題。換句話說(shuō)，他們認(rèn)為空間是一種比時(shí)間更強(qiáng)大的計(jì)算資源

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

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

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

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

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

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

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

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

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

△瓦利安特

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

• 雖然許多問(wèn)題可以用比時(shí)間少得多的空間來(lái)解決，但有些問(wèn)題直觀上似乎需要幾乎與時(shí)間一樣多的空間。

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

于是這個(gè)問(wèn)題就這樣持續(xù)了50年都沒(méi)有解決。

威廉姆斯是怎么解決的？

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

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

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

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

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

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

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

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

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

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

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

從定性角度來(lái)看，威廉姆斯的第二個(gè)結(jié)果聽(tīng)起來(lái)像是人們長(zhǎng)期尋求的P與PSPACE問(wèn)題的解決方案。

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

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

不要要證明PSPACE大于P，研究人員必須進(jìn)一步擴(kuò)大這一差距。但威廉姆斯花了幾個(gè)月的時(shí)間嘗試擴(kuò)展都失敗了。

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

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

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

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

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

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

隨機(jī)選取一種顏色，然后從顯示器中央向隨機(jī)方向發(fā)送。「你永遠(yuǎn)無(wú)法預(yù)測(cè)最終會(huì)得到一個(gè)什么樣的圖像」。

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

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

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

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

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

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

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

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

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

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

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

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

不過(guò)，P 對(duì) PSPACE 這個(gè)問(wèn)題一直在他腦海中揮之不去：我只是想不出什么足夠有趣的東西。

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

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