美國計(jì)算機(jī)協(xié)會10日宣布，普林斯頓高等研究所的艾維·維格森因“對計(jì)算理論的基礎(chǔ)性貢獻(xiàn)，包括重塑我們對隨機(jī)性在計(jì)算中所起作用的理解，以及他在計(jì)算機(jī)理論科學(xué)領(lǐng)域數(shù)十年所取得的卓越成績”榮膺2023年圖靈獎(jiǎng)。
圖靈獎(jiǎng)以已故英國著名數(shù)學(xué)家艾倫·圖靈的名字命名，被譽(yù)為“計(jì)算機(jī)界的諾貝爾獎(jiǎng)”，今年的獎(jiǎng)金為100萬美元。
在硬件層面，計(jì)算機(jī)能以可預(yù)測的方式工作，但這會使其很難對現(xiàn)實(shí)世界的問題進(jìn)行建模，而這些問題往往具有隨機(jī)性和不可預(yù)測性。
在長達(dá)數(shù)十年的職業(yè)生涯中，維格森證明，計(jì)算機(jī)也可利用運(yùn)行算法中的隨機(jī)性。在20世紀(jì)80年代，維格森及其同事發(fā)現(xiàn)，通過在一些算法中插入隨機(jī)性，可使算法更容易、更快地求解。
維格森最重要的發(fā)現(xiàn)之一是明確了問題類型與隨機(jī)性之間的關(guān)系。他還證明，某些包含隨機(jī)性且難以運(yùn)行的算法能變得更具確定性或非隨機(jī)性，且更容易運(yùn)行。這些發(fā)現(xiàn)有助于計(jì)算機(jī)科學(xué)家更好地理解該領(lǐng)域最著名的未經(jīng)證實(shí)的猜想之一，即“P≠NP”。
維格森在20世紀(jì)80年代互聯(lián)網(wǎng)還未出現(xiàn)前就開始探索隨機(jī)性和計(jì)算機(jī)之間的關(guān)系。隨著技術(shù)不斷進(jìn)步，他的想法對從密碼學(xué)到云計(jì)算在內(nèi)的現(xiàn)代計(jì)算應(yīng)用程序變得非常重要。
維格森與以色列魏茨曼科學(xué)研究所的俄德·戈德賴希等人詳細(xì)闡述了在不披露信息的情況下驗(yàn)證信息的方法，即在不同用戶之間建立信任的一種方式，這成為當(dāng)今加密貨幣和區(qū)塊鏈的基礎(chǔ)。（劉霞）
（責(zé)任編輯：蔡文斌）
晉公網(wǎng)安備 14090202000008號 
