交汇点讯 3月17日晚，国际数学界“三大奖”之一、2021年度阿贝尔奖正式揭晓。挪威科学与文学院将奖项授予了匈牙利厄特沃什·罗兰大学教授拉兹洛·洛瓦兹（László Lovász）和美国普林斯顿高等研究院教授艾维·维格森（Avi Wigderson），以表彰他们在理论计算机科学和离散数学方面作出的杰出贡献，使它们逐渐成为现代数学的中心。
阿贝尔奖设立的初衷之一是为了弥补数学界没有诺贝尔奖的遗憾，旨在表彰对数学领域具有“非凡深度和影响力”的贡献。此次获奖的理论计算机科学领域还相对年轻，何以得到了纯数学领域的高度“认可”？新华日报·科技周刊记者联系采访了南京大学计算机科学与技术系教授尹一通，尹一通告诉记者，人类目前对计算的理解还如同“爬树登月”，对新的数学内容和工具有如“登月火箭”般的向往，理论计算机科学被寄予厚望。
什么是“计算复杂性”？
今天，算法和互联网安全应用是我们日常生活中不可或缺的一部分。拉兹洛·洛瓦兹和艾维·维格森的研究在这一发展中发挥了重要作用。
尹一通告诉记者，作为算法和互联网安全应用的理论根基之一的“计算机复杂性”（computational complexity）理论形成于20世纪70年代，现已成为数学和理论计算机科学的成熟领域，“互联网安全应用的理论依据就是包括零知识证明在内的基于计算复杂性理论的现代密码学、网络研究也离不开图论与组合数学工具。这种依赖关系就像是现代飞行器的发展对于空气动力学的依赖、或者以电力为基础的现代工业对电磁学的依赖。”
什么是“计算复杂性”？这与普通人对计算机寻找“最佳算法”的理解有所不同。
“在这个领域，我们不是去为某个问题找到一个高效的算法，这也是人们通常所认为的计算机研究。”尹一通科普道，在计算复杂性的研究中，人们往往要去论证一个计算问题难以解决，从根本上理解一个计算问题因何而难。作为理论计算机科学的子领域，计算复杂性的目的是系统地刻画不同计算问题的必要计算代价——即不同问题的“计算难度”。
尹一通将这种思维通俗地比作小学生分蛋糕的题目，“一个蛋糕分给N个小朋友，最少要切几刀。”尹一通说，如果我们将“分蛋糕”变成各类计算问题，“刀”换成计算设备，“那么切了几刀对应的就是计算的代价，即计算复杂性。”尹一通说，“所有切蛋糕的方案”针对的是无穷多个可能的算法，而不仅仅是人们已知的算法，都要一一论证其解决问题不够高效，依靠的不是穷举，而是数学证明。
这种“不去想办法解决问题，而是找理由说明问题如何困难”的态度，似乎有别于计算机学科的大部分分支，以及社会大众对于计算机学科的预期。尹一通表示，这是因为计算复杂性、乃至理论计算机科学领域都是以科学角度，而非工程角度来看待计算的，“计算的能力与极限客观上是一种自然规律，科学研究的宗旨是为了揭示这一客观真相。”尹一通说，
即便从工科的解决问题的角度出发，理解了解决一个计算问题所要付出的必要代价，也有助于人们找到那个的最聪明的算法。就像在前面切蛋糕的故事中，懂得“怎样切才刀数最少”的小朋友，往往是因为懂得了为何“再少切一刀就一定不行”。
掷骰子能让算法得到更快解答吗？
20世纪70年代，图论（graph theory）成为能够阐明新兴计算复杂性领域的纯数学领域之一。拉兹洛·洛瓦兹曾说，图论并不是主流数学，但计算机科学的迅速发展，让这一情况发生了彻底变化。
尹一通介绍，洛瓦兹在图论、组合数学、算法与计算复杂性等方面都做出了基础性的贡献，例如以他名字命名的洛瓦兹局部引理（Lovász local lemma），这是组合数学中重要的概率法工具，概率法是一类强大的‘非构造化’数学证明方法：为了确定性地证明一个数学命题，却需在证明过程中引入随机性，从而让传统构造性方法无法证明的一些数学命题得到证明。Lovász局部引理目前已成为概率法的基本原理之一，说明了
“随机性对于数学证明可以很有用”
。
有趣的是，另一个获奖者艾维·维格森的成就之一是为“阐明随机性在计算中的作用”提供了一些关键证据，而且这些证据所支持的方向是“随机性对于计算也许没有人们以为的那么有用”。
掷骰子往往能让算法更快找到解答，这一想法其实由来已久。人类在现代电子计算机上实现的最初的几个算法之一，就是由洛斯·阿拉莫斯实验室（Los Alamos national lab）的物理学家们设计的蒙特卡洛（Monte Carlo）随机算法。“艾维·维格森所研究的是，随机性为计算带来的这一便利，是否是不可替代的。”尹一通说，目前人们发现的许多随机算法的确巧妙而且高效，但对于它们解决的问题而言，是否存在一个不依赖随机性的算法来做到类似的事情？维格森的一系列发现，都使得人们逐渐开始觉得，对于一大类计算问题而言，“掷骰子”能让算法更快找到解答，也许只是因为人们尚未发现那个不需要掷骰子的算法——而这样的算法可能始终是存在的。
维格森的另一项重要成果也在信息经济学中发挥着越来越大的影响力，即看起来有点悖论的“零知识证明”（zero-knowledge proofs）——这种证明方式可以让一个人在不透露某个论断内容的情况下，证明这条论断的正确性。
尹一通打了个比方说，我有一项独门秘技，能够区分可口可乐和百事可乐的味道。我希望向我的朋友们证明我真的有这种本事，却不希望他们因此也学会我的秘技。方法就是：让朋友每次随机地倒两杯或相同或不同的可乐，让我来判定这两杯可乐是否是同一种。随着测试次数的增加，如果我总是能答对，则证明了我的确有区分两种可乐的能力。然而，整个过程我都没有透露任何关于这两种可乐哪里不同的知识，这个过程就是零知识证明。
“典型的零知识证明协议恰恰就是依赖非等价性的判定，只不过这里需要判定的，不再是可乐是否是同一种，而是类似于图同构性（graph isomorphism）这种有严格定义的复杂计算问题。”尹一通表示，零知识证明的理论已经被用于支持区块链技术和数字货币上，“身份验证等问题可以归结为对‘我知道一个秘密’的零知识证明，而无需透露关于这个秘密的任何知识”。
计算的边界是一等的数学问题
“现在区分纯数学和应用数学已经越来越困难，不过我认为这是一个很好的发展趋势。”获奖者洛瓦兹的评价也让人们重新审视理论计算机科学与纯数学之间的关系。量子杂志（Quanta Magazine）指出：“上世纪70年代时理论计算机科学和纯数学几乎是完全分开的学科领域，今天，它们已经发展得如此紧密以至于很难找到两者之间的界限。”
尹一通说，事实上，计算机科学最初就是由数学家创立的：哥德尔、图灵、丘奇、冯诺依曼、柯尔莫哥洛夫……这些对于计算机科学而言如普罗米修斯一般的巨人们，他们的职业都是数学家。可以说，在计算机科学诞生的上世纪30-40年代，世间并没有“计算机科学家”，而只有研究计算的数学家。进入上世纪70年代，计算机科学逐渐有了一批成长及活跃于这个学科的理论计算机科学家，形成了自身的学术社区。
“理论计算机科学与数学的联系越来越紧密，有两方面的原因。一是现代计算机科学使用的数学工具越来越高等；另一个更加本质的原因，是理论计算机科学所关注的一部分核心问题，同时也是非常重要的数学问题。”尹一通说。
长久以来都有一个说法，算法是数学世界里的“二等公民”。尹一通举例，一个著名的典故就是：快速傅里叶变换算法的发现，使得现代信号处理、通信和电子工程的大量实践成为了可能，但其数学上的价值远远无法与提出傅里叶变换相比。
“这是公平的，从数学的角度，快速傅里叶变换的确只是傅里叶变换这一数学过程的一个具体实现。但是，假如我们更进一步，问傅里叶变换最快可以有多快，凭什么不能做得更快？”尹一通说，以此类推，问求解一个线性方程组凭什么不能在与读取方程组相当的时间内做到？对于这类问题的探索，就成了第一等的数学问题，因为此时，我们是将计算作为客观的研究对象，希望发现其背后的一般规律。
在克雷数学研究所公布的七个千禧年大奖问题（millennium prize problems）中，头一个就是理论计算机科学领域的P vs NP问题。P代表了可被高效解决的计算问题，NP则代表可高效验证答案正确性的计算问题。“独立找到问题的解，要比看到了解答再验证其正确性困难得多，这是连小学生都有的直观体验。而P≠NP的猜想，就是对这一直观在数学上的严格论证。”尹一通介绍，它的成立与否，也意味着“创造性”是否是客观存在的、是否不可被机械的过程所取代。这一计算复杂性问题也是当今世界七大数学猜想之一。
相对于这个雄心勃勃的使命，目前人类所发展的数学工具都并不胜任，“从著名的P vs NP这一经典难题，到当前的基于深度神经网络的机器学习的理论解释，都非常缺乏合适的数学工具。”尹一通表示，数与计算，都是数学最基本的元件。“计算”是非常核心的数学对象，对计算的本质与界限的理解，必将为数学世界带来全新的内容和变化。
新华日报·交汇点记者 杨频萍
