诺贝尔数学奖（2021年数学界）诺贝尔数学奖(2021年数学)

作者陈大新，维克多

编辑|穆青

3月17日晚，被称为诺贝尔数学奖的阿贝尔奖揭晓。

2021年，挪威科学院决定将阿贝尔奖授予匈牙利约特沃斯·罗兰大学教授拉斯洛·洛瓦什和美国普林斯顿高等研究院教授阿维·维格德森。

以表彰他们“对理论计算机科学和离散数学的基本贡献，以及他们在将理论计算机科学和离散数学推向现代数学中心领域方面的领导作用。”

阿贝尔奖是挪威政府于2001年为纪念挪威著名数学家尼尔斯·亨里克·阿贝尔诞辰200周年而设立的数学奖项。它旨在表彰在数学领域具有非凡深度和影响力的贡献。2003年6月3日，由挪威自然科学和文学院5位数学家组成的委员会正式将该奖颁发给阿贝尔奖的第一位获奖者，之后每年颁发一次，奖金为750万挪威克朗(约合人民币575万元)。

该奖项与菲尔兹奖、沃尔夫数学奖一起，在国际数学领域也被称为“三大奖”。

截至目前，阿贝尔奖已有20多位获奖者，也成为国际公认的诺贝尔数学奖，这也可以看作是对诺贝尔科学奖没有数学奖这一遗憾的一种补救——这也是这一奖项的初衷之一。

理论计算机科学的两位先驱

Lovász和Wigderson是理论计算机科学的先驱，他们的工作为从互联网安全到网络研究的应用奠定了基础。“他们都对理解计算中的随机性和探索有效计算的边界做出了根本性的贡献。”

维格德森表示，该奖项不仅验证了自己工作的意义，也验证了计算理论的价值。他说:“我认为这对这个领域非常重要。”

阿维·维格德森，2021年阿贝尔奖得主(来源:丹·科莫达/美国高等研究院，新泽西州普林斯顿)

Lovász说:“如今，区分纯数学和应用数学越来越难，我认为这是一个很好的发展趋势。”

2021年阿贝尔奖获得者拉斯洛·洛瓦什(来源:匈牙利科学院)

至少从古希腊开始，算法就是数学的中心，甚至是孩子在学校学习的简单程序(比如长除法)。但是自从20世纪计算机出现后，研究的重点已经从“一个算法能解决这个问题吗？”它变成了“一种算法，至少在原理上，可以在合理的时间内在真实的计算机上解决这个问题”。

IAS的数学家彼得·萨纳克说，拉瓦兹和维格德森在这一发展过程中发挥了核心作用。“算法复杂性理论和问题求解速度的研究是在20世纪六七十年代发展起来的，他们被证明是这一领域的绝对领导者。”

“在许多方面，他们的工作是互补的。Lovász学的是数学，而Wigderson学的是计算机科学，但他们研究的很多问题都是相关的。”加州大学圣地亚哥分校的计算机科学家Russell Impagliazzo说，他曾与两名研究人员合作。

洛瓦什和维格德森(奥斯陆，2012。图像来源(Oberwolfach)

2从数学到计算

洛瓦什1948年出生于布达佩斯，成长的环境鼓励有天赋的孩子去竞争解决难题。他从小就是数学明星。十几岁时，他在国际数学奥林匹克竞赛中获得了三枚金牌，并在匈牙利的一次竞赛表演中获得了巨大的胜利，将数学天才们关在玻璃隔离室里，挑战他们独立解决问题的能力。

他早期的大部分灵感来自当代最多产的数学家保罗·erdős。布达佩斯Alfréd Rényi数学研究所的数学家Péter Pál Pálfy说，Erdős专注于离散对象(如网络中的节点)及其关系的数学，而不是几何和其他领域中典型的连续变量。

保罗·erdős将洛夫斯基引入了图论领域。当时，图论是数学中的一个停滞领域，以提出四色定理(现已被证明)等有趣的问题而闻名。定理说，在任何地图中，国家/地区最多只能用四种颜色着色，这样相邻的两个国家/地区就不会使用相同的颜色。

“我不会说它晦涩难懂，但图论最早绝对不是主流数学，因为很多问题只是有趣的谜题。”洛夫茨说。然而，当1970年22岁的洛瓦什拿到博士学位时，情况已经悄然发生了变化，其中一个主要原因是计算机科学的诞生和快速发展。

计算机可以处理离散量(1和0的二进制字符串)，而组合学是离散对象的数学。它的一个主要子领域是图论，研究由连接顶点和边组成的网络。因此，它为研究理论计算机科学中的许多问题提供了强有力的语言。

离散数学中的网络理论曾经被“纯粹”的数学家所轻视，但现在它已经成为其他数学领域和应用(如大数据分析)的至关重要的理论，而Lovász的职业生涯就是在这个时期开始的。他对基础研究及其应用很感兴趣，在微软做了7年的全职研究员，担任过两个学术职务。

Lovász认为计算机和图论的兴起是一个有利的历史共识，可以与一个多世纪前用来分析一个应用物理问题的方法(一种先进的微积分形式)相提并论。Lovász说:“我有时会比较18世纪和19世纪的分析和物理，在这些领域，它们是相互制约的。图论和计算机科学中也发生过类似的事情。”

洛瓦什最著名的成就之一是他与两位荷兰数学理论家阿尔金和亨德里克·伦斯特拉一起设计的算法。这种称为LLL的算法将一个由整数组成的大向量分解成相同类型的最短向量之和。LLL算法适用于称为格的几何对象，格是空中的点集，其坐标通常为整数值。

LLL算法解决了一个关于其属性的基本问题:格中哪一点最接近原点？这个简单的问题通常很难解决，尤其是当它涉及高维空和格之间的点变形时。LLL算法没有完全解决问题，但找到了一个很好的近似解，确定了一个点，并确保没有其他点更接近原点。

由于这种几何模型的广泛适用性，它已被应用于纯数学的各个领域(如分解多项式)，对于数据加密的研究也变得非常重要。基于整数向量的密钥被认为对未来的互联网安全非常重要，因为与今天通信中常用的密钥不同，人们认为它们不会被未来的量子计算机破解。

“这是基本算法之一。它在理论上非常重要，有许多实际用途。”耶路撒冷希伯来大学的IDC Herzliya和Gil Kalai说，他是阿贝尔奖委员会的成员。

Lovász的另一个重要贡献与概率有关。20世纪60年代，保罗·erdős发展了所谓的概率方法来回答关于图的问题。通常，数学家想知道是否存在具有某些属性的图。回答这些问题的一种方法是实际找到一个能够满足条件的图形。但是Erdős意识到，另一种方法证明了随机选择的图形具有这种特性的概率很高。

不幸的是，Erdős\'s概率方法仅在确定具有共同属性的图的存在性时最有效。20世纪70年代，Lovász与Erdős合作设计了一种补充技术，称为Lovász局部引理，以证明非常罕见的图的存在。此后，它成为该领域的主要技术之一。

Lovász在学术生涯中还解决了图论中的许多其他难题，包括Kneser猜想，即给图着色所需的最小颜色数以及保证图与相关结构完美匹配的条件。他还提出了一些自己的猜想，至今仍在指导图论领域的研究，其中包括两个问题，即KLS猜想和EFL猜想，这两个问题直到近几个月才取得重大研究成果。

到目前为止，洛夫茨已经获得了许多荣誉，包括1999年沃尔夫奖、1999年克努斯奖、2001年哥德尔奖和2010年京都奖。

3从计算到数学

维格德森1956年出生于以色列海法。阿贝尔奖承认他对几乎所有计算机科学领域的贡献，在这些领域中，他使用任何他能找到的数学工具来解决任何问题，即使是看似遥远的研究领域。萨纳克说，维格德森对自己研究领域的热情是“有感染力的”。

当他十几岁的时候，计算机科学家刚刚开始起草一个基本的理论框架，这个框架最终贯穿了他的大部分学术生涯。这个框架被称为复杂性理论，它涉及到基于算法难以解决的问题对计算问题进行分类。衡量难度的主要是计算步骤的多少，最基本的区别是“容易”和“难”。

一个简单计算问题的例子是将两个数字相乘。无论数量有多大，电脑都能很快找到产品。这个问题属于“P”的复杂性类，包含了所有容易解决的计算问题。

相比之下，找到一个数的质因数是一个困难的计算问题。没有已知的算法可以快速分解所有数字。然而，如果我们告诉你一个数的质因数，很容易验证它们是否正确。这个问题属于“NP”的复杂性类，它包含了可能很难解决但其答案很容易验证的计算问题。

20世纪70年代初，计算机科学家在计算复杂性领域做出指导性猜想，问P中的问题列表是否正好对应n P中的问题，这就是著名的“P/NP问题”，也是克莱数学研究所千年奖七大难题之一。

这个问题在1977年还是新奇的，当时维格德森也进入了以色列理工学院。在随后的几十年里，维格德森对复杂性理论做出了许多基础性的贡献，比如对一些复杂问题进行分类。

回顾过去，维格德森说，“当我开始读研究生的时候，计算复杂性逐渐开始成熟，在这期间，我自己对问题的理解也加深了”。

20世纪80年代末，维格德森和冉拉兹合作，试图解决计算机复杂度中的完美匹配问题:假设有20台机器，需要执行20个任务，因为每台机器只能完成这些任务的一部分，如何分配机器来完成所有任务，每台机器只能执行一个任务。

维格德森和拉兹提出的解决方案是:增加一些限制，假设处理这个问题的计算机可以执行大多数标准计算(如“与”、“或”)，禁止一些操作，如“非”。

当然，计算机科学家最想证明的是，没有约束，一个计算问题是很难的。但到目前为止，他们还没有做到这一点(否则，我们将知道p是否等于NP)。相反，他们试图证明，当你限制计算资源和可用时间来解决匹配问题时，没有快速算法。

维格德森说:“如果你想找到算法的局限性，当你在最一般的情况下做不到时，你应该限制它，把一只胳膊绑在他们的背上。”1990年，他和Lovász证明，如果数字电路中没有逻辑“非”运算，就没有好的办法用多台计算机并行解决电路中的匹配问题。

自1999年以来，维格德森一直在高等研究院学习。他在复杂性理论方面还取得了许多其他成就，包括一项名为“之字形积”的技术，它可以直接连接到纯数学的许多领域，并提供了一种迷宫策略，其中只需要跟踪固定数量的交叉点。维格德森的工作广度反映了自他加入以来计算复杂性领域的扩展方式。

维格德森另一个最著名的成就是阐明了随机性在计算中的作用。在很多情况下，比如找到迷宫的出路，该算法可以基于隐喻性的抛硬币现象快速找到解决方案。Sarnak说:“如果允许随机选择，许多程序实际上会运行得更快。”

维格德森及其合作者在20世纪90年代发表的两篇论文中证明了在某些假设下，快速随机算法总是可以转化为快速确定性算法。这从理论上保证了随机算法能够真正找到正确的解。结果表明，被称为“BPP”的复杂性类与“P”复杂性类完全相同。它巧妙地将几十年来对随机算法的研究结合到复杂性理论的主题中，并改变了计算机科学家看待随机算法的方式。

维格德森的另一项主要任务在信息经济中越来越重要。它涉及“零知识证明”，这是一种允许某人验证文件的正确性而不泄露其内容的任何信息的方法。

以上就是由优质生活领域创作者 深圳生活网小编 整理编辑的，如果觉得有帮助欢迎收藏转发~