连接数学和计算机科学的先驱赢得了阿贝尔奖

当Avi Wigderson和Lászlóvász于20世纪70年代开始他们的职业生涯时，理论计算机科学和纯数学几乎完全是独立的学科。今天，他们已经长大了，很难找到它们之间的线路。对于这两个领域的许多基本贡献，以及他们一起吸引他们的工作，今天Lovász和Wigderson被授予阿贝尔奖，由挪威科学院和信件颁发的荣誉，并被视为数学中最高荣誉之一。

“在许多方面，他们的作品是互补的。 Avi在计算机科学方面和Lovász正在数学方面，但他们正在努力的许多问题都相关，“加州大学的计算机科学家San Diego合作，俄罗斯大学的计算机科学家都与两位研究人员合作。

这一配对的机会一直发生在他们俩都长大的科学史上的独特时期。

Wigderson于1956年出生于以色列海法，1956年。当他是一名少年时，计算机科学家们刚刚开始绘制一个基本的理论框架，最终会吸收他的大部分职业生活。该框架称为复杂性理论，涉及基于它们的算法如何解决的算法来进行分类计算问题。难度的主要衡量标准是计算步骤的数量，最基本的区别是“简单”与“硬”。

容易计算问题的示例是将两个数字乘以在一起。无论数量多大，计算机都可以快速找到产品。此问题在复杂性类中称为“P”，其中包含所有易于解决的计算问题。

相比之下，找到数字的主要因素是似乎很难的计算问题的一个例子。没有已知的算法可以快速完成所有数字。但是，如果有人向你递给你一个数字的主要因素，那么很容易验证它们是否通过将它们乘以乘以正确的因素。这个问题在于称为“NP”的复杂性类中，其中包含可能难以解决的计算问题，但其答案易于验证。

在20世纪70年代初期，计算机科学家构成了计算复杂性领域的指导猜想，询问P中的问题列表是否完全对应于NP中的问题。

1977年，当威格森进入了以色列技术研究院时，这个问题仍然是新鲜的。在未来几十年中，他将对复杂性理论作出许多基础贡献 - 帮助详细阐述哪些问题在哪些情况下的情况下。

“当我开始研究生院时，计算复杂性正在发展成为一个成熟的领域。我自己开发了它，“Wigderson说。

在20世纪80年代后期，Wigderson和他的合作者Ran Raz研究了“完美匹配”问题的计算复杂性（一个问题在Lovász的工作中也是如此）。假设您已经有了20台机器，每个机器都能够执行20个，但并非所有的任务。完美的匹配问题询问您是否可以将计算机分配给任务，以便覆盖所有任务，并且每台计算机都恰好执行。

Wigderson和Raz研究了这个问题，有一定的限制补充说：他们想象他们对问题的计算机电路有能力大多数标准计算操作（如“和”和“或”），但它无法执行至关重要的计算操作：“不”操作。

当然，计算机科学家最爱，没有资格，计算问题很难。但到目前为止，他们未能这样做（否则我们知道P是否等于NP）。因此，他们试图证明当您限制计算资源以及可用于解决它的时间时，匹配的问题没有快速算法。

“你想找到算法的局限性，如果你不能在最常规的环境中做到这一点，你就会限制他们，你将一只手臂绑在背后，”Wigderson说。 1990年，他和raz证明，没有良好的方式使用许多计算机并行地解决电路中的匹配问题而没有“不”操作。

在同时，Wigderson在复杂性中的核心问题上工作，关于随机性如何改变您可以解决计算问题的速度。自20世纪70年代以来，计算机科学家们怀疑随机性传达了优势。他们发现，如果您在决策过程中允许算法基本上翻转硬币，则可以在某些问题上达到更快的解决方案 - 例如测试数字是否是素数，而不是如果您要求它确定每个步骤。

“这是年龄似乎你可以在没有它的情况下随机做出更多，”Wigderson说。

但在20世纪90年代发表的两篇论文中，Wigderson和他的合作者证明，在某些假设下，始终可以将快速随机算法转换为快速的确定性算法。结果确定称为“BPP”的复杂性级别与复杂性类别完全等于复杂性P.它将数十年的工作与随机算法整齐地绑在复杂性理论的主体中，并改变了计算机科学家研究了随机算法的方式。

“我认为今天几乎任何你问的人会告诉你随机性弱势而不是那种随机性强大，因为，在我们强烈地认为，在我们强烈地认为，可以淘汰随机性，”威格德森说。

自1999年以来一直处于高级研究研究所的Wigderson在复杂性理论中产生了长期的其他结果，包括一种称为Zig-ZAG产品的技术，可以直接连接到纯数学的几个领域，并提供逃脱的策略从迷宫中只能跟踪固定数量的交叉点。 Wigderson的作品的广度反映了计算复杂性领域因他进入它而扩大的方式。

“AVI是该领域的一个非常核心人物，”厄运广场说。 “他是其中一个人作为一个持续的领域将它持有，并且随着我们扩展的明确观点。”

与此同时，Wigderson正在扩大复杂性理论的前沿，Lovász在一个密切相关的领域工作，也有大量的成长空间。

Lovász于1948年出生于布达佩斯，是从早期的数学明星。作为一名少年，他在国际数学奥林匹克赢得了三枚金牌，也在匈牙利的比赛中胜利，将数学潜行的玻璃隔离摊位展示并挑战他们解决问题。

Lovász也在他的生命中，遇到了匈牙利的匈牙利数学家PaulErdīs，他们帮助向他介绍了图表理论的领域。当时，图表理论是一个数学回水，已知为冒充四种颜色猜想（现在被证明的定理）这样的有趣问题，这就询问它是否可以用四种颜色的任何地图彩色，并且没有两个相邻国家的颜色相同。

“我不会称之为模糊，但肯定的图形理论不是主流的数学，因为许多问题或结果来自难题或种类的娱乐数学，”现在在匈牙利·埃斯维斯洛拉姆大学举行的悲观数学。但是，当Lovász于22岁时获得了他的博士学位的时候，事情已经发生了变化，主要原因是计算机科学的出生和快速增长。

通过必要性，计算机使用离散量 - 1S和0s的二进制字符串。组合学是离散物体的数学，其主要子场是图形理论，研究了连接顶点（点）的边缘网络（线）。因此，它为在理论计算机科学中调查了新出现的问题提供了一种语言。

Lovász观看计算机和图表理论的兴起作为卓越的历史同意，与分析的方式（微积分的先进形式）通过调查紧迫的物质问题来到了一个多个世纪。

“我有时会在18世纪和19世纪使用类比来分析和物理，在那里他们用手种植，”Lovász说。 “图表理论和计算机科学中发生了类似类似的东西。”

Lovász的工作中的大部分都是在解决各种问题的算法的发展中。他最有影响力的结果之一是LLL算法，为其创造者，Lovász和兄弟街和Hendrik Lenstra命名。该算法适用于称为格子的几何对象，它们是空间中的点数，其坐标通常具有整数值。 LLL算法解决了关于它们属性的基本问题：格子中的哪一点最接近原点？这是一个简单的问题，通常很难解决，特别是在更高尺寸的空间中，并且当晶格中的点产生扭曲的形状时。

LLL算法而不是完全回答问题，而不是回答问题，识别出一个点并提供保证，即没有其他点较近原点。由于这种几何模型的广泛适用性，发现这一点的能力在广泛的环境中具有影响，从考虑多项式来测试加密系统的安全性。

“这是基本算法之一。理论上，这是重要的，它是为了许多实际目的而用的，“IDC Herzliya和耶路撒冷希伯来大学的吉尔卡莱说，耶路撒冷希伯来大学是亚伯奖委员会的成员。

另一个Lovász最重要的贡献对其具有概率的味道。在20世纪60年代，PaulErdős开发了所谓的概率方法，了解关于图表的问题。数学家通常想知道是否存在具有某些属性的图形。回答这些问题的一种方法是实际找到一个图表。但Erdős意识到另一种方法仅仅是为了证明随机选择的图表将具有高概率的这种属性。

不幸的是，Erdős的概率方法在建立已经常见的图表的存在时最好地工作。在20世纪70年代，Lovász与Erdōs合作设计了一种互补的技术，称为Lovász本地引理，这适合证明存在非常罕见的图形。自从成为该领域的主食之一。

“这是一个工具在随后的证据中使用了数百，数千次，”Kalai说。

Lovász在他的职业生涯中解决了图表理论中的许多其他问题，包括Kneser的猜想，关于着色特定图表所需的最小颜色数，以及关于保证完美匹​​配和图形相关结构的条件的问题。他还产生了几个他自己的猜想，这仍然是今天的图论领域。这些包括两个问题，KLS猜想和EFL猜想，只有在过去几个月内只能看到了很大的结果。

在同一年内，像Wigderson这样的先驱者炼制了我们对计算复杂性的理解，Lovász正在回答有关图表的问题，帮助定义一个复杂性等级和另一个复杂性等级之间的边界。

“这些复杂性概念表现出关于图表的非常简单的问题，”卡莱说。 “所以关于图表的问题变得非常突出，洛美从一开始就研究了这些。”

因此，由Abel奖，它适合将各自领域带到各自的领域的两个先驱者现在加入另一种方式。