W020180517505687875841.jpg
数学界“诺奖”阿贝尔奖揭晓 理论计算机科学,被寄予“登月火箭”般厚望
2021-03-25 08:58:00  来源:新华日报  
1
听新闻

本报记者 杨频萍

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

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

什么是“计算复杂性”

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

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

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

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

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

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

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

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

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

尹一通介绍,洛瓦兹开发解决了各种不同问题的算法,比如算法设计最负盛名的发现是洛瓦兹局部引理算法,这是组合数学中重要的概率法工具,“概率法是一类强 大的‘非构造化’数学证明方法:为了确定性地证明一个数学命题,却需在证明过程中引入随机性,从而让传统构造性方法无法证明的一些数学命题得到证明。”洛 瓦兹局部引理目前已成为概率法的基本原理之一,说明了“随机性对于数学证明可以很有用”。

有趣的是,另一个获奖者艾维维格森的成就之一是为“阐明随机性在计算中的作用”提供了一些关键证据,而且这些证据所支持的方向是“随机性在计算中也许没有本质上的作用”。

掷骰子往往能让算法更快找到解答,这一想法其实由来已久。人类在现代电子计算机上实现的最初的几个算法之一,就是利用了随机性。“艾维维格森所研究的 是,随机性为计算带来的这一便利,是否是不可替代的。”尹一通说,目前人们发现的许多随机算法的确巧妙而且高效,但对于它们解决的问题而言,是否存在一个 不依赖随机性的算法来做到类似的事情?维格森的一系列发现,都使得人们逐渐开始觉得,对于一大类计算问题而言,“掷骰子”能让算法更快找到解答,也许只是 因为人们尚未发现那个不需要掷骰子的算法——而这样的算法可能始终是存在的。

维格森的另一项重要成果也在信息经济学中发挥着越来越大的影响力,即看起来有点悖论的“零知识证明”——这种证明方式可以让一个人在不透露某个论断内容的情况下,证明这条论断的正确性。

尹一通打了个比方说,我有一项独门秘技,能够区分可口可乐和百事可乐的味道。我希望向我的朋友们证明我真的有这种本事,却不希望他们因此也学会我的秘技。 方法就是:让朋友每次随机地倒两杯或相同或不同的可乐,让我来判定这两杯可乐是否是同一种。随着测试次数的增加,如果我总是能答对,则证明了我的确有区分 两种可乐的能力。然而,整个过程我都没有透露任何关于这两种可乐哪里不同的知识,这个过程就是零知识证明。

“典型的零知识证明协议恰恰就是依赖非等价性的判定,只不过这里需要判定的,不再是可乐是否是同一种,而是类似于图同构性这种有严格定义的复杂计算问 题。”尹一通表示,维格森的研究已经被用于区块链技术和数字货币上,“验证方可以用一系列问题来让对方提供‘我知道正确密码’的零知识证明,而无需透露具 体密码。”

计算的边界是一等的数学问题

“现在区分纯数学和应用数学已经越来越困难,不过我认为这是一个很好的发展趋势。”获奖者洛瓦兹的评价也让人们重新审视理论计算机科学与纯数学之间的关 系。量子杂志指出,“20世纪70年代时理论计算机科学和纯数学几乎是完全分开的学科领域,今天,它们已经发展得如此紧密以至于很难找到两者之间的界 限。”

尹一通说,事实上,计算机科学最初就是由数学家创立的:哥德尔、图灵、丘奇、冯诺依曼、柯尔莫哥洛夫……这些对于计算机科学而言如普罗米修斯一般的巨人 们,他们的职业都是数学家。可以说,在计算机科学诞生的上世纪30-40年代,世间并没有“计算机科学家”,而只有研究计算的数学家。进入上世纪70年 代,计算机科学逐渐有了一批成长及活跃于这个学科的理论计算机科学家,形成了自身的学术社区。

“理论计算机科学与数学的联系越来越紧密,有两方面的原因。一是现代计算机科学使用的数学工具越来越高等;另一个更加本质的原因,是理论计算机科学所关注的一部分核心问题,同时也是非常重要的数学问题。”尹一通说。

长久以来都有一个说法,算法是数学世界里的“二等公民”。尹一通举例,一个著名的典故就是:快速傅里叶变换算法的发现,使得现代信号处理、通信和电子工程的大量实践成为了可能,但其数学上的价值远远无法与提出傅里叶变换相比。

“这是公平的,从数学的角度,快速傅里叶变换的确只是傅里叶变换这一数学过程的一个具体实现。但是,假如我们更进一步,问傅里叶变换最快可以有多快,凭什 么不能做得更快?”尹一通说,以此类推,问求解一个线性方程组凭什么不能在与读取方程组相当的时间内做到?对于这类问题的探索,就成了第一等的数学问题, 因为此时,我们是将计算作为客观的研究对象,希望发现其背后的一般规律。

在Clay数学研究所公布的七个千禧年大奖问题中,头一个就是理论计算机科学领域的P vs NP问题。P是一组计算机在数秒内可以轻松解决的问题,NP包含了计算机难以解决的问题,意味着用已知方法可能需要几百万年来找到答案。是否所有困难的问 题都可以转化为简单的问题,即P=NP是成立的吗?这一计算复杂性问题也是当今世界七大数学猜想之一。

相对于这个雄心勃勃的使命,目前人类所发展的数学工具都不胜任,“从著名的P vs NP这一经典难题,到当前的基于深度神经网络的机器学习的理论解释,都非常缺乏合适的数学工具。”尹一通表示,数与计算,都是数学最基本的元件。“计算” 是非常核心的数学对象,对计算的本质与界限的理解,必将为数学世界带来全新的内容和变化。

标签:
责编:梅源
下一篇