編輯：編輯部
【新智元導讀】2023年圖靈獎，剛剛頒給普林斯頓數學教授Avi Wigderson！作為理論計算機科學領域的領軍人物，他對于了解計算中的随機性和僞随機性的作用，做出了開創性貢獻。
2023年圖靈獎，剛剛揭曉！
獲得這屆「計算機界諾貝爾獎」——ACM A.M.圖靈獎的，就是普林斯頓高等研究院數學學院的教授Avi Wigderson。
表彰的是Wigderson在計算理論領域的開創性貢獻，特别是他對計算中随機性角色的重新定義，以及他在理論計算機科學領域數十年的引領。
不僅如此，這一榮譽也使Avi Wigderson成為了，曆史上第一位同時獲得圖靈獎和阿貝爾獎的人。
阿貝爾獎被視為數學領域的最高榮譽
Wigderson是普林斯頓進階研究院數學學院的Herbert H. Maass教授。
他在計算複雜性理論、算法與優化、随機性與密碼學、并行與分布式計算、組合學和圖論等領域均有突出貢獻，并且在理論計算機科學與數學及科學的交叉領域中，也具有重要影響。
最終，他将獲得高達100萬美元的獎金。
計算中的随機性和僞随機性
過去四十年裡，Wigderson對于了解計算中的随機性和僞随機性，做出了開創性貢獻。
此前，計算機科學家們已經發現，随機性與計算難度之間存在顯著的聯系，比如，一些自然問題并沒有高效的算法解決方案。
而Wigderson與同僚合作撰寫了一系列研究，通過增加計算難度，來減少算法中的随機性需求。
這些研究，對于學界具有深遠的影響。
他們成功地證明了，在一些廣泛認可的計算假設下，所有的機率多項式時間算法，都可以被有效轉化為确定性算法。
也即是說，高效的計算并不依賴于随機性。
從此，我們對于計算中随機性作用的了解被徹底改變。
以下就是三篇極具影響力的論文——
- 「Hardness vs. Randomness」（與Noam Nisan合著）
這篇論文不僅引入了一種新型僞随機發生器，而且還證明了：在比以前所知更弱的假設下，可以對随機算法進行高效确定性模拟。
- 「BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs」（與László Babai、Lance Fortnow和Noam Nisan合著）
這篇論文利用「難度放大」，證明了在弱假設下，可以在亞指數時間内模拟無限多輸入長度的有限錯誤機率多項式時間（BPP）。
- 「P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma」（與Russell Impagliazzo合著）
這篇論文介紹了一種更強的僞随機發生器，它在本質上實作了難度與随機性之間的最優權衡。
Wigderson的這三篇論文，其理論被廣泛應用于理論計算機科學的多個分支，并且激發了多位專家的重要研究。
在計算中随機性的廣泛領域内，Wigderson與Omer Reingold、Salil Vadhan和Michael Capalbo合作，首次高效構造了展開圖，這些圖具有出色的稀疏性和連通性，廣泛應用于數學和理論計算機科學中。
上下滑動
除了随機性研究，Wigderson還在多證明者互動式證明、密碼學和電路複雜度等多個理論計算機科學領域，發揮了重要的上司作用。
此外，他作為導師和同僚也備受贊譽。他的親和力、熱情和慷慨，吸引了衆多青年學者，投身理論計算機科學領域。
複雜性理論先驅
作為一名計算複雜性理論家，相比于問題的答案，讓Avi Wigderson更感興趣的是，這些問題是否有解決方案？以及，該如何進行判斷？
「對于我們正在面對并嘗試解決的每一個問題，都不能排除存在一種能夠解決它的算法。這是我認為最有趣的問題。」
如今，Wigderson憑借着在計算理論基礎上的傑出貢獻，榮獲了公認的最高榮譽之一——ACM A.M.圖靈獎。
Wigderson的父親非常熱愛拼圖和數學基本原理。
而在以色列海法長大的Wigderson，深受父親的影響，
「他讓我對這個領域産生了濃厚的興趣，」Wigderson回憶道。
1970年代，Wigderson在海法大學開始了大學生涯。
最初他本主修數學，但在父母的建議下轉向了計算機科學。而這背後的原因很樸素——他的父母認為，這個專業更好找工作。
雖然沒去成數學專業，但Wigderson很快就發現，計算機科學是一個充滿了未解之謎的領域，而這些謎題，本質上都與數學相關。
他早期的一項開創性工作，正是探讨這樣一個看似沖突的問題——
能否在不展示證明過程的情況下讓人相信：一個數學命題已經得到了證明？
1985年，Shafi Goldwasser、Silvio Micali和Charles Rackoff首次提出了零知識互動證明的概念，并展示了其在若幹命題上的應用。
後來，Wigderson與Micali和Oded Goldreich一起進一步闡述了這一理論，明确了這一點——
如果一個命題可以被證明，那麼它也可以有一個零知識證明。
有了零知識證明，我們就可以證明自己使用密鑰正确加密或簽名了資訊，同時不洩露任何相關的細節。
對此，普林斯頓大學的計算機科學家Ran Raz評價道：「Avi在密碼學領域有許多極其重要的成果，而這，就最重要的那個。」
不過，Wigderson最最具奠基性的成就，可能在于另一個領域：将計算難度與随機性相聯系。
到了1970年代末，計算機科學家們已經發現，對于許多難題，采用随機性算法（也稱為機率算法）會顯著優于傳統的确定性算法。
例如，1977年，Robert Solovay和Volker Strassen提出了一種随機算法，可以比當時最好的确定性算法更快地判斷一個數字是否為質數。
對某些問題而言，機率算法則可以引出确定性算法。
在1980年代初，Wigderson與加州大學伯克利分校的Richard Karp合作，将随機性的思想應用于那些被認為計算上極其困難的問題，也就是那些不存在已知的确定性算法能在合理時間内解決的問題。
很快，Wigderson和Karp就發現了一個難題的随機算法，并最終成功将其轉化為了确定性算法。
與此同時，其他研究人也展示了，如何在密碼學問題中通過計算難度的假設來實作去随機化。
由此，Wigderson也和其他人一樣，開始質疑在有效解決問題時随機性的必要性，以及在什麼條件下可以完全去除随機性。
随後他意識到，對随機性的需求與問題的計算難度緊密相連。
在1994年的一篇論文中，Wigderson與計算機科學家Noam Nisan共同證明——
如果真如大多數計算機科學家所猜測的那樣，存在自然界中的困難問題，那麼，任何高效的随機算法都可以被高效的确定性算法替代。
也就是說，随機性總是可以被消除的。
更為重要的是，他們發現确定性算法可能使用「僞随機」序列——這些資料串看起來随機，但實際上不是。
同時，他們還展示了如何利用任意難題來建構僞随機生成器。即通過将僞随機比特（不是真正的随機比特）輸入到機率算法中，就可以為同一問題生成一個高效的确定性算法。
Sudan指出，這篇論文幫助計算機科學家們認識到随機性的不同程度，進而幫助揭示了難題的複雜性及其解決方法。「這其中的關鍵不僅僅是随機性，而是對随機性的認知，」他說。
如今，随機性已經成為複雜性理論中的一個強大工具，但它非常難以捉摸。
Wigderson指出，像硬币擲出和骰子擲出這樣的行為，并不是真正的随機：如果你對這些實體系統有足夠的了解，那麼其結果是完全可以預測的。
但完美的随機性既難以捉摸也難以驗證。
在過去幾十年裡，來自計算理論的發現幫助我們深入了解了許多意想不到的問題，從鳥群的集體飛行、選舉結果到體内的生化反應。
最後，我們用Wigerson的一句話總結作為總結——計算的應用無處不在。
「基本上，任何自然過程都可以被視為一種演化的計算過程，是以我們可以從計算的角度來研究它。可以說，幾乎所有事物都在進行某種形式的計算。」
Wigerson還曾在2009年獲得了哥德爾獎。
2018年，Wigerson因對計算機科學和數學理論的貢獻（Institute for Advanced Study）當選ACM Fellow。他還在2019年獲得了高德納獎。
補充知識
什麼是理論計算機科學？
理論計算機科學專注于計算領域的數學基礎。
它探讨的問題包括，「這個問題能否通過計算來解決？」，以及「如果這個問題可以通過計算解決，需要投入多少時間和其他資源？」
此外，理論計算機科學還緻力于設計高效的算法。每一項觸及我們生活的計算技術都是通過算法實作的。
深入了解構成強大和高效算法的原理，不僅能增進我們對計算機科學的認識，還能幫助我們更好地了解自然規律。
盡管理論計算機科學以其提供的激動人心的智力挑戰而聞名，且通常不直接關注計算的實際應用改進，但該領域的研究成果已在從密碼學、計算生物學到網絡設計、機器學習及量子計算等幾乎所有子領域推動了顯著進展。
為什麼随機性很重要？
一般來說，計算機是确定性系統——算法的指令集對任何特定輸入都有唯一确定的計算過程和輸出結果。
也就是說，确定性算法遵循一個可預測的模式。
然而，随機性則不同，它沒有明确的模式，也無法預測事件或結果的發生。
鑒于我們所處的世界似乎充斥着随機事件（如天氣系統、生物和量子現象等），計算機科學家們通過讓算法在計算過程中進行随機選擇，以期提高算法的效率。
事實上，許多以前沒有有效的确定性算法解決方案的問題，現在通過機率算法得到了有效的解決，雖然這些算法可能會有小機率的錯誤（但這種錯誤可以有效地減少）。
但是，随機性是否是必要的，還是可以去除它？成功的機率算法需要什麼樣的随機性？
這些問題以及其他許多基本問題構成了了解計算中随機性和僞随機性的核心。
更深入地了解計算中随機性的動态可以幫助我們開發更優秀的算法，并深化我們對計算本質的了解。
參考資料：
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