快科技4月11日消息，昨天晚間計算機協(xié)會ACM宣布，將“計算機界最高榮譽”圖靈獎授予復(fù)雜性理論先驅(qū)、普林斯頓高等研究院教授艾維·維格森（Avi Wigderson）。

維格森教授在2021年還獲得了被譽為“數(shù)學(xué)界諾貝爾獎”的阿貝爾獎，其也成為首個同時拿下數(shù)學(xué)和計算機最高獎的科學(xué)家。

值得一提的是，他還是2017年阿里達摩院剛成立時首批“十大祖師”之一

ACM表示，這是對維格森教授在計算理論的基礎(chǔ)性貢獻，包括塑造對計算中隨機性作用的理解，以及數(shù)十年來在理論計算機科學(xué)領(lǐng)域卓越領(lǐng)導(dǎo)力的表彰。

作為一名數(shù)學(xué)家和計算機科學(xué)家，維格森在計算復(fù)雜性理論、算法和優(yōu)化、隨機性和密碼學(xué)、并行和分布式計算、組合學(xué)、圖論以及理論計算機科學(xué)與數(shù)學(xué)、科學(xué)之間的關(guān)聯(lián)等領(lǐng)域都是領(lǐng)軍學(xué)者。

維格森最重要的貢獻，就是增強了人類對計算中隨機性和偽隨機性作用的理解。

簡單來說，20世紀(jì)70年代末，科學(xué)家們發(fā)現(xiàn)對于許多難題，采用隨機性的算法（也稱為概率算法）可以遠(yuǎn)遠(yuǎn)勝過其確定性方案。

而在20世紀(jì)80年代，維格森與Richard Karp合作，發(fā)現(xiàn)了一種針對某個難題的隨機算法，然后發(fā)現(xiàn)：能夠?qū)⑵淙ルS機化，從而有效地揭示了它的確定性算法。

在1994年，維格森和Noam Nisan證明，如果存在任何自然難題，那么每一種有效的隨機算法都可以被有效的確定性算法所取代。

更重要的是，他們還發(fā)現(xiàn)確定性算法可能使用“偽隨機”序列——也就是看似隨機但實際上并非隨機的數(shù)據(jù)串。

這一系列研究徹底改變了計算機科學(xué)家對隨機性的看法，并適用于理論計算機科學(xué)的許多領(lǐng)域。

ACM將圖靈獎這一重要榮譽頒給了維格森，主要嘉獎的就是他在如上領(lǐng)域的貢獻。