第666章 2021年度阿贝尔奖揭晓：这是计算机与数学的共荣时代

        但是自从20世纪计算机问世以来，学界研究的方式与兴趣发生了根本性的转向，很多数学家已不再满足于仅仅寻找解决问题的特定算法，他们转而考虑探索算法本身的性质，以及计算的边界问题。 一个可计算问题被认为是一个原则上可以用计算机解决的问题，换言之，这个问题同样可以在一系列机械的数学步骤下得到解决，例如算法。这成为了理论计算机科学的出发点之一。 而离散数学和理论计算机科学的完美结合，为信息时代诸多新兴技术、理论提供了基石。 但将时间倒推至50年前，理论计算机科学和纯数学尚还是各自独立的领域。 人们将很难想象，它们在不久的将来会成为枝叶相接、难以分割的交叉学科。 Lovász说：“现在区分纯数学和应用数学已经越来越困难，不过我认为这是一个很好的发展趋势。” Lovász研究的主要影响之一是确立了离散数学能够解决计算机科学基本理论问题的方法。 1972年，他解出了“完美图猜想”，该猜想是图理论中一个长期存在的开放性问题； 1978年，他使用代数拓扑证明了Kneser猜想，轰动了学界； 1979 年，他解决了信息理论中的经典问题，确定了五边形图的“香农容量“； Lovász 在算法设计领域最负盛名的发现是 Lovász局部引理。 Lovász 还参与了一篇有关概率可检测证明定理（PCP定理）的论文，该论文现已发展成为计算复杂性最重要的领域之一。 而除了致力于计算机科学的基础工作外，Lovász还设计了功能强大、应用广泛的算法，例如LLL算法。 该算法由Lovász与Arjen Lenstra和Hendrik Lenstra一同创立，算法也因此命名为“Lenstra-Lenstra-Lovasz（LLL）”。 LLL格基约化算法自1982年被提出以来，已被成功应用于计算机代数、编码理论、密码分析、算法数论、整数规划等众多领域，显示出了非凡的发展潜力。 Wigderson深化了数学和计算机科学之间的联系，他研究了随机性在辅助计算中的作用。 他以能够发现明显不相关的领域之间的联系而闻名。 他与Omer Reingold 和Salil Vadhan一起发展的Zig-zag graph product就是一个示例。 Zig-zag graph product将组合理论、图理论与复杂性理论相关联，并在应用方面取得了惊人的效果。 Wigderson的另一个成就是对零知识证明做出了根本性的贡献，这一密码学领域的新概念，现在正被应用于区块链技术。     喜欢数学大帝请大家收藏：(www.663d.com)数学大帝六六闪读更新速度最快。