将数学与计算机科学联系起来的先驱者获得数学诺贝尔奖 | quantamagazine

21-03-26 banq

阿贝尔奖(Abel Prize,也称为亚伯奖)是一项挪威设立的数学界大奖,每年颁发一次。被认为数学界的诺贝尔奖。 Avi Wigderson(威格森)和LászlóLovász(洛瓦兹)分别因其开发复杂性理论和图论的工作以及将这两个领域联系在一起而获奖。

在1970年代,理论计算机科学和纯数学几乎是完全独立的学科。今天,它们之间的距离是如此之近,以至于很难找到它们之间的界线。由于他们在这两个领域的许多基本贡献以及将他们融合在一起的工作,威格森在计算机科学方面,而洛瓦兹在数学方面,但是他们从事的许多问题都是相关的,今天洛瓦兹和威格森被授予阿贝尔奖,这是挪威科学与文学学院颁发的荣誉,被视为数学领域的最高荣誉之一。

 

威格森的复杂性理论

威格森(Wigderson)于1956年出生于以色列海法。在他十几岁的时候,计算机科学家才刚刚开始草拟一个基本的理论框架,该框架称为复杂性理论,涉及基于算法难以解决的问题对计算问题进行分类。难度的主要衡量标准是计算步骤的数量,最基本的区别是“简单”与“困难”。(P和NP问题)

通俗易懂的P vs NP问题解释 -@AlejandroPiad

1970年代初期,计算机科学家提出了计算复杂度方面的指导性猜想,询问P中的问题列表是否恰好与NP中的问题相对应?

这个问题在1977年威格森进入以色列理工学院Technion时仍然很新鲜。

在接下来的几十年里,他将为复杂性理论做出许多基础性的贡献-帮助阐明在何种情况下哪些问题属于哪种复杂性类别。

在1980年代后期,威格森和他的合作者Ran Raz研究了“完美匹配”问题(这也是洛瓦兹作品中的一个问题)的计算复杂性。假设您有20台机器,每台机器都可以执行20个不同任务中的一些(但不是全部)。完美匹配的问题询问您是否可以将计算机分配给任务,以便涵盖所有任务,并且每台计算机仅执行一个任务。

威格森和Raz研究了该问题,并添加了某些限制:他们认为处理该问题的计算机电路能够执行大多数标准的计算操作(例如“ and”和“ or”),但是它不能执行关键的操作:“not”操作。

当然,计算机科学家最希望无条件地证明计算问题很难解决。但是到目前为止,他们还没有这样做到(否则我们会知道P是否等于NP)。因此,相反,他们尝试证明在限制计算资源以及解决该问题所需的时间时,对于匹配之类的问题没有快速的算法。

算法的局限性:如果在最一般的情况下无法做到,就必须加以限制,将一只手臂绑在他们的背后。

 在1990年,他和Raz证明,如果没有“not”操作,则没有很好的方法并行使用许多计算机来解决电路中的匹配问题。

大约在同一时间,威格森研究了一个复杂性的中心问题,即随机性如何改变解决计算问题的速度。自1970年代以来,计算机科学家一直怀疑随机性会带来优势。他们发现,如果允许算法在决策过程中发生类似抛硬币,那么与某些问题(例如测试数字是否为质数)确定性地选择每个步骤相比,可以更快地找到解决方案。

但是在1990年代发表的两篇论文中,威格森和他的合作者证明,在某些假设下,总是有可能将快速随机算法转换为快速确定性算法。结果确定了被称为“ BPP”的复杂性类与“ P”复杂性类完全相同。它将数十年来对随机算法的研究巧妙地结合到了复杂性理论的主体中,并改变了计算机科学家看待随机算法的方式。

随机性很弱,而不是随机性很强,因为在我们坚信的假设下,可以消除随机性。

 

洛瓦兹的图论

洛瓦兹(Lovász)于1948年出生在布达佩斯,从小就算是数学界的明星。十几岁的时候,他在国际数学奥林匹克竞赛上获得了三枚金牌,并且在匈牙利的一场比赛表演中大获全胜。

那个时候图论不但晦涩难懂,也不是主流数学,当洛瓦兹在1970年22岁时获得博士学位时,情况已经发生了变化:一个主要原因是计算机科学的诞生和迅速发展。

根据需要,计算机可以处理离散量-1和0的二进制字符串。组合学是离散对象的数学,它的主要子领域之一是图论,它研究连接顶点(点)的边(线)网络。这样,它为研究理论计算机科学中出现的问题提供了一种语言。

洛瓦兹的许多工作都集中在解决各种问题的算法的开发上。他最有影响的结果之一是LLL算法,该算法以其创建者Lovász以及Arjen和Hendrik Lenstra兄弟命名。该算法适用于称为晶格的几何对象,这些几何对象是空间中的点集,其坐标通常具有整数值。LLL算法解决了有关其属性的一个基本问题:晶格中的哪个点最接近原点?这是一个简单的问题,通常很难解决,尤其是在高维空间中以及晶格中的点何时形成变形的形状。

LLL算法没有完全回答问题,而是找到了一个很好的近似值,确定了一个点并确保没有其他点更接近原点。由于此几何模型的广泛适用性,找到这一点的能力在从分解多项式到测试密码系统安全性的各种设置中都具有意义。

洛瓦兹(Lovász)最重要的贡献是在概率上。在1960年代,PaulErdős开发了所谓的概率方法来回答有关图的问题。1970年代,Lovász与Erdős合作设计了一种补充技术,称为Lovász局部引理,用于证明非常稀有的图的存在。

洛瓦兹在其职业生涯中解决了图论中的许多其他问题,包括Kneser的猜想,关于为特定图着色所需的最小颜色数以及有关保证图完美匹配和相关结构的条件的问题。他还产生了他自己的一些猜想,这些猜想如今仍在指导图论领域。其中包括两个问题,即KLS猜想和EFL猜想,仅在最近几个月内才取得了重大成果。

 

在像威格森这样的先驱者加深了我们对计算复杂性的理解的同一年,洛瓦兹回答了有关图的问题,这些图有助于定义一个复杂性类与另一个复杂性类之间的边界。

这些复杂性概念通过图论得以非常简单的体现,两个将各自领域融为一体的先驱者现在以另一种方式获得了亚伯奖,这很合适。

 

1
猜你喜欢