阿貝爾獎(jiǎng)和圖靈獎(jiǎng)常被稱為數(shù)學(xué)界和計(jì)算機(jī)界的諾貝爾獎(jiǎng)。此前，從未有人同時(shí)獲得這兩個(gè)大獎(jiǎng)，直到現(xiàn)在，數(shù)學(xué)家阿維·維格森（Avi Wigderson）成為了史上首個(gè)榮獲這兩個(gè)獎(jiǎng)項(xiàng)的科學(xué)家。

4月10日，美國計(jì)算機(jī)學(xué)會(huì)（ACM）宣布將2023年圖靈獎(jiǎng)授予維格森，以表彰他對計(jì)算理論的基礎(chǔ)性貢獻(xiàn)。維格森的工作幾乎觸及了這一學(xué)科的每一個(gè)領(lǐng)域。他的同事、合作者和學(xué)員都說，他總是能在不同的領(lǐng)域之間發(fā)現(xiàn)意想不到的橋梁。從20世紀(jì)90年代開始，他對隨機(jī)性和計(jì)算所展開的研究工作，就為數(shù)學(xué)和計(jì)算機(jī)科學(xué)之間建立了深刻的聯(lián)系。

1956年，維格森出生在以色列海法。他是計(jì)算復(fù)雜性理論、算法和優(yōu)化、隨機(jī)性和密碼學(xué)、并行和分布式計(jì)算、組合學(xué)、圖論等領(lǐng)域的先驅(qū)。除了剛剛榮獲的圖靈獎(jiǎng)，他還與洛瓦茲·拉茲洛 （Lovász László）在2021年一同榮獲了數(shù)學(xué)領(lǐng)域的最高獎(jiǎng)——阿貝爾獎(jiǎng)。（圖/Peter Badge）

隨機(jī)性與確定性 

從本質(zhì)上說，計(jì)算機(jī)是確定性系統(tǒng)。確定性算法遵循的是可預(yù)測的模式。相比之下，隨機(jī)性缺乏明確的模式，或者說缺乏對事件或結(jié)果的可預(yù)測性。

在20世紀(jì)70年代末，許多計(jì)算機(jī)科學(xué)家已經(jīng)意識到，對于許多難題，采用隨機(jī)性的算法，即概率算法，遠(yuǎn)勝于確定性算法。許多沒有有效確定性算法的問題，都可以被概率算法有效地解決，盡管存在一些小的出錯(cuò)率。

隨機(jī)性的令人驚訝的有效性，引發(fā)計(jì)算機(jī)科學(xué)家思考隨機(jī)性本身的本質(zhì)，他們開始質(zhì)疑隨機(jī)性對于有效解決問題有多必要，以及在什么情況下它是可以被完全移除的。

這些問題，以及許多其他相關(guān)的基本問題，是理解計(jì)算中隨機(jī)和偽隨機(jī)的核心。更好地理解計(jì)算中的隨機(jī)動(dòng)態(tài)，有助于科學(xué)家發(fā)展出更好的算法，并加深對計(jì)算的本質(zhì)的理解。

維格森的貢獻(xiàn)  

維格森在計(jì)算機(jī)科學(xué)的各個(gè)領(lǐng)域都作出了廣泛而深刻的貢獻(xiàn)，而他將隨機(jī)性與困難問題聯(lián)系起來的工作，可能是其中最為顯著的成就。

維格森與合作者發(fā)表了一系列極具影響力的論文。在20世紀(jì)90年代發(fā)表的兩篇論文中，他與合作者證明了在特定的假設(shè)下，對于高效計(jì)算來說，隨機(jī)性并不是必需的。

他們提出了一個(gè)有點(diǎn)類似于P≠NP的猜想，P=BPP，這個(gè)等式意味著每個(gè)隨機(jī)算法都可以被去隨機(jī)化，并轉(zhuǎn)化為具有可觀效率的確定性算法；此外，去隨機(jī)化是通用且普遍的，它不依賴于隨機(jī)化算法的內(nèi)部細(xì)節(jié)。

另一種看待這個(gè)問題的方式是將其視為難度和隨機(jī)性之間的權(quán)衡：如果存在一個(gè)足夠困難的問題，那么隨機(jī)性就可以通過高效的確定性算法進(jìn)行模擬。維格森隨后證明了與之相反的觀點(diǎn)，他得出的結(jié)論認(rèn)為：即使是針對具有已知隨機(jī)算法的特定問題的有效確定性算法，也意味著一定存在這樣一個(gè)困難問題。

這一工作與偽隨機(jī)（看起來隨機(jī)）的對象緊密相關(guān)。維格森的工作構(gòu)建了偽隨機(jī)生成器，它將幾個(gè)真正隨機(jī)的比特變成許多偽隨機(jī)比特，從一個(gè)不完美的隨機(jī)源中提取出近乎完美的隨機(jī)比特。

維格森的這些工作的影響，遠(yuǎn)遠(yuǎn)超出了隨機(jī)和去隨機(jī)領(lǐng)域。他的這些想法隨后被應(yīng)用于理論計(jì)算機(jī)科學(xué)的眾多領(lǐng)域。

維格森并沒有止步于此，他仍致力于研究計(jì)算隨機(jī)性的廣泛領(lǐng)域。在另一組論文中，他給出了擴(kuò)展圖（具有強(qiáng)連通性的稀疏圖）的第一個(gè)有效的組合結(jié)構(gòu)，這些擴(kuò)展圖在數(shù)學(xué)和理論計(jì)算機(jī)科學(xué)中都有許多重要應(yīng)用。

指導(dǎo)與傳承 

除了在學(xué)術(shù)上做出了突破性的貢獻(xiàn)外，維格森還被公認(rèn)為一位受人尊敬的導(dǎo)師和同事，他為無數(shù)年輕的研究人員無私地提供建議。他淵博的知識和無與倫比的技術(shù)，加上他的友好、熱情和慷慨，吸引了許多最優(yōu)秀的年輕人從事理論計(jì)算機(jī)科學(xué)的研究。