數(shù)學(xué) + 計(jì)算機(jī)科學(xué) = 2021年阿貝爾獎(jiǎng)
2021年阿貝爾獎(jiǎng)獲得者László Lovász。圖片來源：Hungarian Academy of Sciences/Laszlo Mudra
上個(gè)世紀(jì)70年代，當(dāng) Avi Wigderson 和 László Lovász 開始他們的職業(yè)生涯時(shí)，理論計(jì)算機(jī)科學(xué)和純數(shù)學(xué)幾乎是完全分開的學(xué)科領(lǐng)域。經(jīng)過幾十年的發(fā)展，這兩個(gè)學(xué)科之間早已變得極為密切，我們甚至很難分清它們之間的界限。今天，Wigderson和Lovász二人因其在理論計(jì)算機(jī)科學(xué)和離散數(shù)學(xué)所作出的基礎(chǔ)性貢獻(xiàn)，獲得了數(shù)學(xué)領(lǐng)域的最高獎(jiǎng)之一——阿貝爾獎(jiǎng)。
編譯 | 佐 佑
● ● ●
理論計(jì)算機(jī)科學(xué)研究的是計(jì)算的能力和局限，其根源可追溯到庫(kù)爾特·哥德爾、阿隆佐·丘奇、阿蘭·圖靈，以及約翰·馮·諾伊曼的基礎(chǔ)工作，這些工作為真正的物理計(jì)算機(jī)研究的發(fā)展奠定了堅(jiān)實(shí)的基礎(chǔ)。
理論計(jì)算機(jī)科學(xué)包含了兩個(gè)互補(bǔ)的子學(xué)科，一個(gè)是算法設(shè)計(jì)，另一個(gè)是計(jì)算復(fù)雜性。前者涉及到為大量的計(jì)算問題開發(fā)有效的方法，后者展示了算法效率存在固有的局限性。20世紀(jì)60年代，Alan Cobham 等人提出了多項(xiàng)式時(shí)間算法的概念，Stephen Cook 等人提出了著名的P≠NP猜想。這些工作對(duì)整個(gè)領(lǐng)域以及Lovász和Wigderson的工作，都產(chǎn)生了重大影響。
理論計(jì)算機(jī)科學(xué)是密碼學(xué)的基礎(chǔ)，且它對(duì)其他一些科學(xué)領(lǐng)域的影響正日漸明顯。圖形、字符串、排列等離散結(jié)構(gòu)都是理論計(jì)算機(jī)科學(xué)的核心，離散數(shù)學(xué)和理論計(jì)算機(jī)科學(xué)也自然成了緊密相關(guān)的領(lǐng)域。雖然這兩個(gè)領(lǐng)域都從傳統(tǒng)的數(shù)學(xué)領(lǐng)域中獲益良多，但現(xiàn)在反向的影響也越來越大。理論計(jì)算機(jī)科學(xué)所帶來的應(yīng)用、概念和技術(shù)，激發(fā)了更多新的挑戰(zhàn)，開辟了新的研究方向，并解決了純數(shù)學(xué)和應(yīng)用數(shù)學(xué)中的一些重要的未解難題。
在過去的幾十年里，Lovász和Wigderson一直是這一領(lǐng)域中的領(lǐng)軍人物。他們的工作在許多方面都有交叉，尤其是他們都為理解計(jì)算中的隨機(jī)性，以及探索高效計(jì)算的邊界，做出了杰出貢獻(xiàn)。
1948年，Lovász出生于匈牙利布達(dá)佩斯。年輕時(shí)的Lovász就已是數(shù)學(xué)界的一顆閃耀新星，他在十幾歲時(shí)就在國(guó)際數(shù)學(xué)奧林匹克競(jìng)賽上獲得了三枚金牌。
Lovász最具影響力的成果之一，就是與Arjen Lenstra和Hendrik Lenstra 一起創(chuàng)立了以他們?nèi)嗣置?strong>LLL算法。這是最基本的算法之一，它不僅在理論上很重要，在很多實(shí)際用途上也很重要。LLL算法適用于被稱為格的幾何對(duì)象，格指的是在空間中其坐標(biāo)值通常為整數(shù)值的點(diǎn)集。LLL算法解決了關(guān)于格的屬性的一個(gè)基本問題：格中的哪個(gè)點(diǎn)離原點(diǎn)最近？這是一個(gè)難以解決的問題，尤其是在高維空間中，以及格中的點(diǎn)會(huì)形成失真的形狀時(shí)。
LLL算法不能精確地解答這個(gè)問題，但卻能找到一個(gè)很好的近似。它能確定一個(gè)點(diǎn)，并保證沒有其他任何點(diǎn)比這個(gè)點(diǎn)更接近原點(diǎn)。這一幾何模型有著廣泛的適用性，找到這個(gè)點(diǎn)在許多應(yīng)用場(chǎng)景中都有重要意義。LLL算法除了能分解有理多項(xiàng)式等應(yīng)用之外，它還是密碼專家最喜歡的工具，它已成功地破解了幾個(gè)密碼系統(tǒng)。而令人稱奇的是，對(duì)LLL算法的分析也能被用于設(shè)計(jì)和保證更新的基于格的密碼系統(tǒng)（甚至可抵擋量子計(jì)算機(jī)的攻擊）的安全性。
LLL算法只是Lovász眾多有遠(yuǎn)見的貢獻(xiàn)之一。除了LLL算法，這位高產(chǎn)的數(shù)學(xué)家還證明了局部引理；展示了如何有效地解決半定規(guī)劃，由此引領(lǐng)了一場(chǎng)算法設(shè)計(jì)的革命；他為隨機(jī)漫步理論及其在歐幾里得等周問題和高維物體近似體積計(jì)算中的應(yīng)用做出了貢獻(xiàn)；他與 Uriel Feige 等人發(fā)表的論文證明了一個(gè)早期版本的概率可檢測(cè)證明定理（PCP定理）；他還解決了長(zhǎng)期存在的完美圖猜想、Kneser猜想等問題，并在近年來發(fā)展了圖極限理論。
2021年阿貝爾獎(jiǎng)獲得者 Avi Wigderson。圖片來源：Dan Komoda/Institute for Advanced Study, Princeton, NJ USA
Wigderson于1956年出生在以色列海法。在他十幾歲時(shí)，計(jì)算機(jī)科學(xué)家們才剛剛開始勾畫復(fù)雜性理論的基本框架。復(fù)雜性理論關(guān)注的是算法的速度和效率，它涉及到根據(jù)算法解決計(jì)算問題時(shí)的難度對(duì)問題進(jìn)行分類。
Wigderson對(duì)計(jì)算復(fù)雜性的各個(gè)方面都做出了廣泛而深刻的貢獻(xiàn)，尤其是隨機(jī)性在計(jì)算中的作用。在過去的幾十年里，一些研究人員為許多問題發(fā)展了確定性算法，而此前只有隨機(jī)算法是已知的。由Agrawal等人提出的確定性算法的素?cái)?shù)檢測(cè)就是去隨機(jī)化算法的一個(gè)顯著例子。
這樣的去隨機(jī)化的成果，讓數(shù)學(xué)家們開始思考隨機(jī)性是否真的重要的問題。在20世紀(jì)90年代發(fā)表的兩篇論文中，Wigderson和他的合作者證明了在特定的假設(shè)下，答案很可能是否定的。他們提出了一個(gè)有點(diǎn)類似于P≠NP的猜想，P=BPP，這個(gè)等式意味著每個(gè)隨機(jī)算法都可以被去隨機(jī)化，并轉(zhuǎn)化為具有可觀效率的確定性算法；此外，去隨機(jī)化是通有且普遍的，它不依賴于隨機(jī)化算法的內(nèi)部細(xì)節(jié)。
另一種看待這項(xiàng)工作的方式是將其視為難度和隨機(jī)性之間的權(quán)衡：如果存在一個(gè)足夠困難的問題，那么隨機(jī)性就可以通過高效的確定性算法進(jìn)行模擬。Wigderson隨后證明了與之相反的觀點(diǎn)，他得出的結(jié)論認(rèn)為：即使是針對(duì)具有已知隨機(jī)算法的特定問題的有效確定性算法，也意味著一定存在這樣一個(gè)困難問題。
這一工作與偽隨機(jī)（看起來隨機(jī)）的對(duì)象緊密相關(guān)。Wigderson的工作構(gòu)建了偽隨機(jī)生成器，它將幾個(gè)真正隨機(jī)的比特變成許多偽隨機(jī)比特，從一個(gè)不完美的隨機(jī)源中提取出近乎完美的隨機(jī)比特。他與 Omer Reingold 以及 Salil Vadhan 一起發(fā)展出的鋸齒形圖積，啟發(fā)了 Irit Dinur 對(duì)PCP定理的組合證明，以及Reingold對(duì)圖連通性問題的高效存儲(chǔ)算法。
Wigderson的貢獻(xiàn)還不止于此，他對(duì)密碼學(xué)基礎(chǔ)的貢獻(xiàn)，為無需通過任何物理手段發(fā)展出像在線撲克游戲一樣復(fù)雜的協(xié)議奠定了基礎(chǔ)。他在交互式證明系統(tǒng)方面的研究，尤其是在 “零知識(shí)證明” 這一悖論式的概念上的研究，最近已經(jīng)被用于區(qū)塊鏈技術(shù)和數(shù)字貨幣上。工業(yè)、醫(yī)藥、在線通信、電子商務(wù)和經(jīng)濟(jì)中的數(shù)字創(chuàng)新，全部都依賴于算法和復(fù)雜性理論的研究。
這些想法徹底改變了科學(xué)領(lǐng)域，而這僅僅是個(gè)開始。像Wigderson和Lovász這樣的學(xué)者將繼續(xù)對(duì)這些基礎(chǔ)性問題及其潛在影響進(jìn)行研究。在Lovász和Wigderson的領(lǐng)導(dǎo)下，離散數(shù)學(xué)和相對(duì)年輕的理論計(jì)算機(jī)科學(xué)領(lǐng)域現(xiàn)正在逐漸成為現(xiàn)代數(shù)學(xué)的中心。
參考資料：
https://www.abelprize.no
制版編輯 | 盧卡斯
