【新智元導(dǎo)讀】2023 年圖靈獎，剛剛頒給普林斯頓數(shù)學(xué)教授 Avi Wigderson！作為理論計算機(jī)科學(xué)領(lǐng)域的領(lǐng)軍人物，他對于理解計算中的隨機(jī)性和偽隨機(jī)性的作用，作出了開創(chuàng)性貢獻(xiàn)。
2023 年圖靈獎，剛剛揭曉！
獲得這屆「計算機(jī)界諾貝爾獎」——ACM A.M.圖靈獎的，就是普林斯頓高等研究院數(shù)學(xué)學(xué)院的教授 Avi Wigderson。
表彰的是 Wigderson 在計算理論領(lǐng)域的開創(chuàng)性貢獻(xiàn)，特別是他對計算中隨機(jī)性角色的重新定義，以及他在理論計算機(jī)科學(xué)領(lǐng)域數(shù)十年的引領(lǐng)。
不僅如此，這一榮譽(yù)也使 Avi Wigderson 成為了，歷史上第一位同時獲得圖靈獎和阿貝爾獎的人。
阿貝爾獎被視為數(shù)學(xué)領(lǐng)域的最高榮譽(yù)
Wigderson 是普林斯頓高級研究院數(shù)學(xué)學(xué)院的 Herbert H. Maass 教授。
他在計算復(fù)雜性理論、算法與優(yōu)化、隨機(jī)性與密碼學(xué)、并行與分布式計算、組合學(xué)和圖論等領(lǐng)域均有突出貢獻(xiàn)，并且在理論計算機(jī)科學(xué)與數(shù)學(xué)及科學(xué)的交叉領(lǐng)域中，也具有重要影響。
最終，他將獲得高達(dá) 100 萬美元的獎金。
計算中的隨機(jī)性和偽隨機(jī)性
過去四十年里，Wigderson 對于理解計算中的隨機(jī)性和偽隨機(jī)性，做出了開創(chuàng)性貢獻(xiàn)。
此前，計算機(jī)科學(xué)家們已經(jīng)發(fā)現(xiàn)，隨機(jī)性與計算難度之間存在顯著的聯(lián)系，比如，一些自然問題并沒有高效的算法解決方案。
而 Wigderson 與同事合作撰寫了一系列研究，通過增加計算難度，來減少算法中的隨機(jī)性需求。
這些研究，對于學(xué)界具有深遠(yuǎn)的影響。
他們成功地證明了，在一些廣泛認(rèn)可的計算假設(shè)下，所有的概率多項式時間算法，都可以被有效轉(zhuǎn)化為確定性算法。
也即是說，高效的計算并不依賴于隨機(jī)性。
從此，我們對于計算中隨機(jī)性作用的理解被徹底改變。
以下就是三篇極具影響力的論文 ——
「Hardness vs. Randomness」（與 Noam Nisan 合著）
這篇論文不僅引入了一種新型偽隨機(jī)發(fā)生器，而且還證明了：在比以前所知更弱的假設(shè)下，可以對隨機(jī)算法進(jìn)行高效確定性模擬。
「BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs」（與 László Babai、Lance Fortnow 和 Noam Nisan 合著）
這篇論文利用「難度放大」，證明了在弱假設(shè)下，可以在亞指數(shù)時間內(nèi)模擬無限多輸入長度的有限錯誤概率多項式時間（BPP）。
「P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma」（與 Russell Impagliazzo 合著）
這篇論文介紹了一種更強(qiáng)的偽隨機(jī)發(fā)生器，它在本質(zhì)上實(shí)現(xiàn)了難度與隨機(jī)性之間的最優(yōu)權(quán)衡。
Wigderson 的這三篇論文，其理論被廣泛應(yīng)用于理論計算機(jī)科學(xué)的多個分支，并且激發(fā)了多位專家的重要研究。
在計算中隨機(jī)性的廣泛領(lǐng)域內(nèi)，Wigderson 與 Omer Reingold、Salil Vadhan 和 Michael Capalbo 合作，首次高效構(gòu)造了展開圖，這些圖具有出色的稀疏性和連通性，廣泛應(yīng)用于數(shù)學(xué)和理論計算機(jī)科學(xué)中。
除了隨機(jī)性研究，Wigderson 還在多證明者交互式證明、密碼學(xué)和電路復(fù)雜度等多個理論計算機(jī)科學(xué)領(lǐng)域，發(fā)揮了重要的領(lǐng)導(dǎo)作用。
此外，他作為導(dǎo)師和同事也備受贊譽(yù)。他的親和力、熱情和慷慨，吸引了眾多青年學(xué)者，投身理論計算機(jī)科學(xué)領(lǐng)域。
復(fù)雜性理論先驅(qū)
作為一名計算復(fù)雜性理論家，相比于問題的答案，讓 Avi Wigderson 更感興趣的是，這些問題是否有解決方案？以及，該如何進(jìn)行判斷？
「對于我們正在面對并嘗試解決的每一個問題，都不能排除存在一種能夠解決它的算法。這是我認(rèn)為最有趣的問題?！?/p>
如今，Wigderson 憑借著在計算理論基礎(chǔ)上的杰出貢獻(xiàn)，榮獲了公認(rèn)的最高榮譽(yù)之一 ——ACM A.M.圖靈獎。
Wigderson 的父親非常熱愛拼圖和數(shù)學(xué)基本原理。
而在以色列海法長大的 Wigderson，深受父親的影響，
「他讓我對這個領(lǐng)域產(chǎn)生了濃厚的興趣，」Wigderson 回憶道。
1970 年代，Wigderson 在海法大學(xué)開始了大學(xué)生涯。
最初他本主修數(shù)學(xué)，但在父母的建議下轉(zhuǎn)向了計算機(jī)科學(xué)。而這背后的原因很樸素 —— 他的父母認(rèn)為，這個專業(yè)更好找工作。
雖然沒去成數(shù)學(xué)專業(yè)，但 Wigderson 很快就發(fā)現(xiàn)，計算機(jī)科學(xué)是一個充滿了未解之謎的領(lǐng)域，而這些謎題，本質(zhì)上都與數(shù)學(xué)相關(guān)。
他早期的一項開創(chuàng)性工作，正是探討這樣一個看似矛盾的問題 ——
能否在不展示證明過程的情況下讓人相信：一個數(shù)學(xué)命題已經(jīng)得到了證明？
1985 年，Shafi Goldwasser、Silvio Micali 和 Charles Rackoff 首次提出了零知識交互證明的概念，并展示了其在若干命題上的應(yīng)用。
后來，Wigderson 與 Micali 和 Oded Goldreich 一起進(jìn)一步闡述了這一理論，明確了這一點(diǎn) ——
如果一個命題可以被證明，那么它也可以有一個零知識證明。
有了零知識證明，我們就可以證明自己使用密鑰正確加密或簽名了信息，同時不泄露任何相關(guān)的細(xì)節(jié)。
對此，普林斯頓大學(xué)的計算機(jī)科學(xué)家 Ran Raz 評價道：「Avi 在密碼學(xué)領(lǐng)域有許多極其重要的成果，而這，就最重要的那個?！?/p>
不過，Wigderson 最最具奠基性的成就，可能在于另一個領(lǐng)域：將計算難度與隨機(jī)性相聯(lián)系。
到了 1970 年代末，計算機(jī)科學(xué)家們已經(jīng)發(fā)現(xiàn)，對于許多難題，采用隨機(jī)性算法（也稱為概率算法）會顯著優(yōu)于傳統(tǒng)的確定性算法。
例如，1977 年，Robert Solovay 和 Volker Strassen 提出了一種隨機(jī)算法，可以比當(dāng)時最好的確定性算法更快地判斷一個數(shù)字是否為質(zhì)數(shù)。
對某些問題而言，概率算法則可以引出確定性算法。
在 1980 年代初，Wigderson 與加州大學(xué)伯克利分校的 Richard Karp 合作，將隨機(jī)性的思想應(yīng)用于那些被認(rèn)為計算上極其困難的問題，也就是那些不存在已知的確定性算法能在合理時間內(nèi)解決的問題。
很快，Wigderson 和 Karp 就發(fā)現(xiàn)了一個難題的隨機(jī)算法，并最終成功將其轉(zhuǎn)化為了確定性算法。
與此同時，其他研究人也展示了，如何在密碼學(xué)問題中通過計算難度的假設(shè)來實(shí)現(xiàn)去隨機(jī)化。
由此，Wigderson 也和其他人一樣，開始質(zhì)疑在有效解決問題時隨機(jī)性的必要性，以及在什么條件下可以完全去除隨機(jī)性。
隨后他意識到，對隨機(jī)性的需求與問題的計算難度緊密相連。
在 1994 年的一篇論文中，Wigderson 與計算機(jī)科學(xué)家 Noam Nisan 共同證明 ——
如果真如大多數(shù)計算機(jī)科學(xué)家所猜測的那樣，存在自然界中的困難問題，那么，任何高效的隨機(jī)算法都可以被高效的確定性算法替代。
也就是說，隨機(jī)性總是可以被消除的。
更為重要的是，他們發(fā)現(xiàn)確定性算法可能使用「偽隨機(jī)」序列 —— 這些數(shù)據(jù)串看起來隨機(jī)，但實(shí)際上不是。
同時，他們還展示了如何利用任意難題來構(gòu)建偽隨機(jī)生成器。即通過將偽隨機(jī)比特（不是真正的隨機(jī)比特）輸入到概率算法中，就可以為同一問題生成一個高效的確定性算法。
Sudan 指出，這篇論文幫助計算機(jī)科學(xué)家們認(rèn)識到隨機(jī)性的不同程度，從而幫助揭示了難題的復(fù)雜性及其解決方法?！高@其中的關(guān)鍵不僅僅是隨機(jī)性，而是對隨機(jī)性的認(rèn)知，」他說。
如今，隨機(jī)性已經(jīng)成為復(fù)雜性理論中的一個強(qiáng)大工具，但它非常難以捉摸。
Wigderson 指出，像硬幣擲出和骰子擲出這樣的行為，并不是真正的隨機(jī)：如果你對這些物理系統(tǒng)有足夠的了解，那么其結(jié)果是完全可以預(yù)測的。
但完美的隨機(jī)性既難以捉摸也難以驗證。
在過去幾十年里，來自計算理論的發(fā)現(xiàn)幫助我們深入理解了許多意想不到的問題，從鳥群的集體飛行、選舉結(jié)果到體內(nèi)的生化反應(yīng)。
最后，我們用 Wigerson 的一句話總結(jié)作為總結(jié) —— 計算的應(yīng)用無處不在。
「基本上，任何自然過程都可以被視為一種演化的計算過程，因此我們可以從計算的角度來研究它。可以說，幾乎所有事物都在進(jìn)行某種形式的計算?！?/p>
Wigerson 還曾在 2009 年獲得了哥德爾獎。
2018 年，Wigerson 因?qū)τ嬎銠C(jī)科學(xué)和數(shù)學(xué)理論的貢獻(xiàn)（Institute for Advanced Study）當(dāng)選 ACM Fellow。他還在 2019 年獲得了高德納獎。
補(bǔ)充知識
什么是理論計算機(jī)科學(xué)？
理論計算機(jī)科學(xué)專注于計算領(lǐng)域的數(shù)學(xué)基礎(chǔ)。
它探討的問題包括，「這個問題能否通過計算來解決？」，以及「如果這個問題可以通過計算解決，需要投入多少時間和其他資源？」
此外，理論計算機(jī)科學(xué)還致力于設(shè)計高效的算法。每一項觸及我們生活的計算技術(shù)都是通過算法實(shí)現(xiàn)的。
深入理解構(gòu)成強(qiáng)大和高效算法的原理，不僅能增進(jìn)我們對計算機(jī)科學(xué)的認(rèn)識，還能幫助我們更好地理解自然規(guī)律。
盡管理論計算機(jī)科學(xué)以其提供的激動人心的智力挑戰(zhàn)而聞名，且通常不直接關(guān)注計算的實(shí)際應(yīng)用改進(jìn)，但該領(lǐng)域的研究成果已在從密碼學(xué)、計算生物學(xué)到網(wǎng)絡(luò)設(shè)計、機(jī)器學(xué)習(xí)及量子計算等幾乎所有子領(lǐng)域推動了顯著進(jìn)展。
為什么隨機(jī)性很重要？
一般來說，計算機(jī)是確定性系統(tǒng) —— 算法的指令集對任何特定輸入都有唯一確定的計算過程和輸出結(jié)果。
也就是說，確定性算法遵循一個可預(yù)測的模式。
然而，隨機(jī)性則不同，它沒有明確的模式，也無法預(yù)測事件或結(jié)果的發(fā)生。
鑒于我們所處的世界似乎充斥著隨機(jī)事件（如天氣系統(tǒng)、生物和量子現(xiàn)象等），計算機(jī)科學(xué)家們通過讓算法在計算過程中進(jìn)行隨機(jī)選擇，以期提高算法的效率。
事實(shí)上，許多以前沒有有效的確定性算法解決方案的問題，現(xiàn)在通過概率算法得到了有效的解決，雖然這些算法可能會有小概率的錯誤（但這種錯誤可以有效地減少）。
但是，隨機(jī)性是否是必要的，還是可以去除它？成功的概率算法需要什么樣的隨機(jī)性？
這些問題以及其他許多基本問題構(gòu)成了理解計算中隨機(jī)性和偽隨機(jī)性的核心。
更深入地理解計算中隨機(jī)性的動態(tài)可以幫助我們開發(fā)更優(yōu)秀的算法，并深化我們對計算本質(zhì)的理解。
參考資料：
https://www.acm.org/
https://awards.acm.org/turing
https://www.quantamagazine.org/avi-wigderson-complexity-theory-pioneer-wins-turing-award-20240410/
https://www.ias.edu/news/avi-wigderson-2023-acm-am-turing-award
本文來自微信公眾號：新智元 （ID：AI_era）
廣告聲明：文內(nèi)含有的對外跳轉(zhuǎn)鏈接（包括不限于超鏈接、二維碼、口令等形式），用于傳遞更多信息，節(jié)省甄選時間，結(jié)果僅供參考，IT之家所有文章均包含本聲明。