第666章 2021年度阿貝爾獎揭曉：這是計算機與數學的共榮時代

但是自從20世紀計算機問世以來，學界研究的方式與興趣發生了根本性的轉向，很多數學家已不再滿足於僅僅尋找解決問題的特定演算法，他們轉而考慮探索演算法本身的性質，以及計算的邊界問題。

一個可計算問題被認為是一個原則上可以用計算機解決的問題，換言之，這個問題同樣可以在一系列機械的數學步驟下得到解決，例如演算法。這成為了理論計算機科學的出發點之一。

而離散數學和理論計算機科學的完美結合，為信息時代諸多新興技術、理論提供了基石。

但將時間倒推至50年前，理論計算機科學和純數學尚還是各自獨立的領域。

人們將很難想象，它們在不久的將來會成為枝葉相接、難以分割的交叉學科。

Lovász說：「現在區分純數學和應用數學已經越來越困難，不過我認為這是一個很好的發展趨勢。」

Lovász研究的主要影響之一是確立了離散數學能夠解決計算機科學基本理論問題的方法。

1972年，他解出了「完美圖猜想」，該猜想是圖理論中一個長期存在的開放性問題；

1978年，他使用代數拓撲證明了Kneser猜想，轟動了學界；

1979年，他解決了信息理論中的經典問題，確定了五邊形圖的「香農容量「；

Lovász在演算法設計領域最負盛名的發現是Lovász局部引理。

Lovász還參與了一篇有關概率可檢測證明定理（PCP定理）的論文，該論文現已發展成為計算複雜性最重要的領域之一。

而除了致力於計算機科學的基礎工作外，Lovász還設計了功能強大、應用廣泛的演算法，例如LLL演算法。

該演算法由Lovász與ArjenLenstra和HendrikLenstra一同創立，演算法也因此命名為「Lenstra-Lenstra-Lovasz（LLL）」。

LLL格基約化演算法自1982年被提出以來，已被成功應用於計算機代數、編碼理論、密碼分析、演算法數論、整數規劃等眾多領域，顯示出了非凡的發展潛力。

Wigderson深化了數學和計算機科學之間的聯繫，他研究了隨機性在輔助計算中的作用。

他以能夠發現明顯不相關的領域之間的聯繫而聞名。

他與OmerReingold和SalilVadhan一起發展的Zig-zaggraphproduct就是一個示例。

Zig-zaggraphproduct將組合理論、圖理論與複雜性理論相關聯，並在應用方面取得了驚人的效果。

Wigderson的另一個成就是對零知識證明做出了根本性的貢獻，這一密碼學領域的新概念，現在正被應用於區塊鏈技術。

。