Pioneers Linking Math and Computer Science Win the Abel Prize

将数学和计算机科学联系起来的先驱获得阿贝尔奖

作者: Kevin Hartnett

来源: Quanta Magazine, March 17, 2021.

（翻译：Dr. Lee）

艾维·维格森（Avi Wigderson）和拉兹洛·洛瓦兹（László Lovász）由于在发展复杂性理论和图论、以及建立两个领域之间联系上的贡献获得阿贝尔奖。

2021 Abel Prize winners Avi Wigderson in New Jersey in 2021 and László Lovász at the Hungarian Academy of Sciences in 2019.Dan Komoda, Institute for Advanced Study; Hungarian Academy of Sciences, László Mudra

当艾维·维格森和拉兹洛·洛瓦兹在1970年代开始他们的职业时，理论计算机科学和纯数学几乎是两个完全分离的学科。今天，它们已经发展得如此紧密以至于很难找到两者之间的界线。由于他们对这两个领域的许多基础性贡献，并且由于他们的工作将这两个领域靠拢，今天洛瓦兹和维格森被授予阿贝尔奖，一个由挪威科学和文学院颁发的荣誉，是数学领域的最高荣誉之一。

“在许多方面他们的工作是互补的。艾维来自计算机科学，洛瓦兹来自数学，但是他们研究的许多问题都是相关的，”罗素·因帕利亚佐（Russell Impagliazzo）说，他是加州大学圣地亚哥分校的计算机科学家，与两位研究者都有过合作。

发生在两人身上的机遇完全是由于科学史上一段独一无二的时期，他们随之成长起来。

维格森1956年出生在以色列海法。在他的少年时期，计算机科学家正要开始构思一个基础理论框架，那最终占据了他的大部分职业生涯。那个框架，被称作复杂性理论，涉及对计算问题进行分类，依据的是它们用算法求解的难度。衡量难度的主要指标是计算的步数，只有“易”和“难”两个最基本的区别。

一个容易计算的例子是两个数相乘。无论数变得多么大，计算机都能迅速找到它们的积。这个问题在复杂性分类中属于“P”类，它包含所有容易计算的问题。

作为对比，找到一个整数的素数因子是一个难以计算的例子。没有已知的算法可以对所有的整数迅速得到结果。但是如果有人递给你某个数的素因子，容易证明它们就是这个数正确的素因子因为只需要把它们乘起来。这个问题在复杂性分类中属于“NP”类，它包含所有很难求解但是答案容易验证的计算问题。

在1970年代早期，计算机科学家在计算复杂性领域形成了一个有影响的猜想，它问是否P中的问题与NP中的问题对应。

这个问题在维格森1977年进入以色列理工学院时仍保持着热度。在接下来的数十年里他在复杂性理论上做出了许多基础性的贡献---阐明在什么条件下哪一个问题属于哪一类。

“当我开始研究生学习时，计算复杂性正在发展成为成熟的领域。我自己随之一起发展，”维格森说。

在1980年代后期，维格森和他的合作者然·拉茨（Ran Raz）研究“完美匹配”问题的计算复杂性（这个问题也出现在洛瓦兹的工作中）。假设你有20个机器，每一个能执行20个不同任务中的一些但不是全部。完美匹配问题问你是否可以给机器分配任务，使得所有的任务都被执行并且每一个机器只执行一个任务。

维格森和拉茨在加入某种限制下研究这个问题：他们想象执行这个任务的计算机电路能执行最标准的运算（像“和”与“或”），但是不能执行一个关键的操作：“非”运算。

当然，计算机科学家最喜欢在没有条件限制下证明一个计算问题是难的。但是到目前为止他们还没有成功（否则我们会知道P是否等于NP）。 所以他们代之以证明在你限制了计算资源以及求解的时间后一个问题例如匹配没有快速算法。

“你想找到算法的极限，并且如果你在最一般的条件下做不到，你就限制它们，你把一条胳膊绑在它们自己身后，”维格森说。在1990年他和拉茨证明了在没有“非”运算下没有好的方法能够使用多个并行计算机求解匹配问题。

与此同时，维格森还在研究复杂性的一个中心问题，关于随机性怎样改变你求解计算问题的速度。从1970年代开始，计算机科学家猜测随机性具有优势。他们已经发现如果你允许算法在决策过程中主要依赖抛硬币，它对一些问题能更快地得到解---比如验证一个数是否是素数---比你要求算法确定性地选择每一步要快。

“那段时期你使用随机性看起来要比不使用它能做更多的事，”维格森说。

但是在1990年代发表的两篇论文中，维格森和他的合作者们证明在某些假设下，总是可以转换一个快速随机算法到一个快速确定性算法。这个结果表明这个被叫做"BPP"复杂性的类与“P”类复杂性相同。它把关于随机化算法几十年的工作完美地绑定到复杂性理论主体中，改变了计算机科学家对随机性算法的看法。

“我认为今天几乎你问到的每一个人会告诉你随机性是弱的而不是随机性很强大，因为在一定假设下我们足以相信随机性可以被消除，”维格森说。

维格森，从1999年开始在普林斯顿高等研究院工作，已经在复杂性理论中产生了一连串的结果，包括一个叫做zig-zag积的技术，它直接连接到一些纯数学领域，还提供了一个在仅跟踪固定数目的交叉时逃离迷宫的策略。维格森工作的宽度反映出计算复杂性理论领域从他进入以来扩张的路径。

“艾维在这个领域是一个核心人物，”因帕利亚佐说。他是一个能够把它形成一个持续发展的领域的人物之一，并且在我们扩张它时他有清晰的视野。

在维格森开拓复杂性理论的前沿时，洛瓦兹工作在一个密切相关的领域，那里也有许多发展的空间。

Lovász and Wigderson already knew each other well; here they are chatting at the Abel Prize Lectures in Oslo in 2012.Gert-Martin Greue; Source: Archives of the Mathematisches Forschungsinstitut Oberwolfach

1948年出生于布达佩斯，洛瓦兹很早就成为数学明星。在少年时期他获得了三块国际数学奥林匹克金牌，还在一个匈牙利电视竞赛秀中获胜，在那个节目中数学神童们进入用玻璃隔离的房间参加求解问题的挑战。

还是在他生涯的早期，洛瓦兹遇到了匈牙利著名数学家保罗·厄尔多斯（Paul Erdős），在他的帮助下接触到图论领域。那时图论如同数学中的一潭死水，能被人所知的是提出有趣的问题比如四色猜想（现在已被证明），它问是否总可以只用四种颜色给地图中的国家涂色使得没有两个相邻的国家有相同的颜色。

“我不能说它无人知晓，但是可以肯定图论不是主流数学因为许多问题或者结果来自谜题或者娱乐数学，”洛瓦兹说，他现在在匈牙利厄特沃什·罗兰大学（Eötvös Loránd Universit）工作。但是到洛瓦兹在1970年22岁获得博士学位时形式已经在改变---一个主要的原因是计算机科学的出现和迅速的发展。

计算机必然要处理离散的量---1和0的二进制字符串。组合是离散事物的数学，它的一个主要子领域是图论，研究由边连接点构成的网络。因此，它提供了一种语言探究理论计算机科学中出现的问题。

洛瓦兹把计算机和图论的崛起视为历史上一段美妙的共生时期，与之相提并论的是一个多世纪之前的分析（微积分的高级形式）产生于对紧迫的物理问题的研究中。

“我有时用产生于18和19世纪的分析和物理做类比，那时它们手拉手齐头并进，”洛瓦兹说。“发生在图论和计算机科学中的事有相似之处。”

洛瓦兹的大部分工作围绕着发展解不同问题的算法。它最有影响的一个结果是LLL算法，以它的发明者洛瓦兹和阿仁·伦斯特拉（Arje Lenstr）、亨德里克·伦斯特拉（Hendrik Lenstra）兄弟的名字命名。这个算法研究一种叫做格（lattice）的几何对象，它们是空间中坐标通常为整数的点集。LLL算法解决了它们的一个基本问题：格中的哪一个点离原点最近？它是个简单的问题却常常难于求解，尤其是在高维空间以及当格中的点形成一个扭曲的形状时。

代替精确回答这个问题，LLL算法找到了一个好的逼近，找到一个点并且确保没有其他点更接近原点。由于这个几何模型广泛的应用性，确定这个点可以应用到更广泛的问题中，从因式分解多项式到测试密码系统的安全性。

“它是一个基础算法。它在理论上和许多实践应用上都很重要，”赫兹利亚跨学科研究中心和希伯来大学的吉尔·卡莱说，他原先是阿贝尔奖委员会的成员。

洛瓦兹另一个最有意义的贡献有一个概率特色。在1960年代保罗·厄尔多斯发展了一个概率方法回答关于图论的问题。数学家们经常想知道有某种属性的图是否存在。一种回答这些问题的方法是找到这样一个图。但是厄尔多斯意识到还有一种方法是只需要证明随机选择的一个图会有很高的概率具有这个属性。

不幸的是，厄尔多斯的概率方法对于常见的图在建立它们的存在性时表现最好。在1970年代，洛瓦兹与厄尔多斯合作设计了一个补充的技术，叫做洛瓦兹局部引理（ Lovász local lemma），可以证明那些稀有的图的存在性。从那时起它就变成了这个领域的基础技术之一。

“这是一个在后来的证明中被使用了成百上千次的工具，”卡莱说。

洛瓦兹在他的职业生涯中解决了图论的许多问题，包括克内泽尔猜想（Kneser’s conjecture），关于对一个图上色所需颜色的最小数量，以及关于保证完美匹配和图中的相关结构所需条件的一个问题。他也产生了自己的一些猜想，它们在今天仍然在图论领域发挥着作用。这包括两个问题，KLS猜想和EFL猜想，在过去的几个月中才看到一些大的进展出现。

在这些年里当先驱像维格森在改进我们对计算复杂性的理解时，洛瓦兹在回答关于图的问题，用它们来定义不同复杂性类之间的边界。

“这些复杂性概念可以用关于图的非常简单的问题来表示，”卡莱说。“所以关于图的问题变得非常重要，并且洛瓦兹从最开始就在研究。”

那么，两个先驱他们曾推进各自领域的发展，如今以另一种方式联系在一起，这非常合适，阿贝尔奖委员会说。