探索 | 数学“诺奖”阿贝尔奖揭晓——理论计算机科学，被寄予“登月火箭”般厚望

交汇点讯 3月17日晚，国际数学界“三大奖”之一、2021年度阿贝尔奖正式揭晓。挪威科学与文学院将奖项授予了匈牙利厄特沃什·罗兰大学教授拉兹洛·洛瓦兹（László Lovász）和美国普林斯顿高等研究院教授艾维·维格森（Avi Wigderson），以表彰他们在理论计算机科学和离散数学方面作出的杰出贡献，使它们逐渐成为现代数学的中心。

阿贝尔奖设立的初衷之一是为了弥补数学界没有诺贝尔奖的遗憾，旨在表彰对数学领域具有“非凡深度和影响力”的贡献。此次获奖的理论计算机科学领域还相对年轻，何以得到了纯数学领域的高度“认可”？新华日报·科技周刊记者联系采访了南京大学计算机科学与技术系教授尹一通，尹一通告诉记者，人类目前对计算的理解还如同“爬树登月”，对新的数学内容和工具有如“登月火箭”般的向往，理论计算机科学被寄予厚望。

什么是“计算复杂性”？

今天，算法和互联网安全应用是我们日常生活中不可或缺的一部分。拉兹洛·洛瓦兹和艾维·维格森的研究在这一发展中发挥了重要作用。

尹一通告诉记者，作为算法和互联网安全应用的理论根基之一的“计算机复杂性”（computational complexity）理论形成于20世纪70年代，现已成为数学和理论计算机科学的成熟领域，“互联网安全应用的理论依据就是包括零知识证明在内的基于计算复杂性理论的现代密码学、网络研究也离不开图论与组合数学工具。这种依赖关系就像是现代飞行器的发展对于空气动力学的依赖、或者以电力为基础的现代工业对电磁学的依赖。”

什么是“计算复杂性”？这与普通人对计算机寻找“最佳算法”的理解有所不同。

“在这个领域，我们不是去为某个问题找到一个高效的算法，这也是人们通常所认为的计算机研究。”尹一通科普道，在计算复杂性的研究中，人们往往要去论证一个计算问题难以解决，从根本上理解一个计算问题因何而难。作为理论计算机科学的子领域，计算复杂性的目的是系统地刻画不同计算问题的必要计算代价——即不同问题的“计算难度”。

尹一通将这种思维通俗地比作小学生分蛋糕的题目，“一个蛋糕分给N个小朋友，最少要切几刀。”尹一通说，如果我们将“分蛋糕”变成各类计算问题，“刀”换成计算设备，“那么切了几刀对应的就是计算的代价，即计算复杂性。”尹一通说，“所有切蛋糕的方案”针对的是无穷多个可能的算法，而不仅仅是人们已知的算法，都要一一论证其解决问题不够高效，依靠的不是穷举，而是数学证明。

这种“不去想办法解决问题，而是找理由说明问题如何困难”的态度，似乎有别于计算机学科的大部分分支，以及社会大众对于计算机学科的预期。尹一通表示，这是因为计算复杂性、乃至理论计算机科学领域都是以科学角度，而非工程角度来看待计算的，“计算的能力与极限客观上是一种自然规律，科学研究的宗旨是为了揭示这一客观真相。”尹一通说，

即便从工科的解决问题的角度出发，理解了解决一个计算问题所要付出的必要代价，也有助于人们找到那个的最聪明的算法。就像在前面切蛋糕的故事中，懂得“怎样切才刀数最少”的小朋友，往往是因为懂得了为何“再少切一刀就一定不行”。

掷骰子能让算法得到更快解答吗？

20世纪70年代，图论（graph theory）成为能够阐明新兴计算复杂性领域的纯数学领域之一。拉兹洛·洛瓦兹曾说，图论并不是主流数学，但计算机科学的迅速发展，让这一情况发生了彻底变化。

尹一通介绍，洛瓦兹在图论、组合数学、算法与计算复杂性等方面都做出了基础性的贡献，例如以他名字命名的洛瓦兹局部引理（Lovász local lemma），这是组合数学中重要的概率法工具，概率法是一类强大的‘非构造化’数学证明方法：为了确定性地证明一个数学命题，却需在证明过程中引入随机性，从而让传统构造性方法无法证明的一些数学命题得到证明。Lovász局部引理目前已成为概率法的基本原理之一，说明了

“随机性对于数学证明可以很有用”