您现在的位置: 首页 > 网站导航收录 > 百科知识百科知识

(诺贝尔数学奖)-2021年数学界

问题,算法,数学(诺贝尔数学奖)-2021年数学界

发布时间：2016-12-08加入收藏来源：互联网点击：

截至目前，Lovász已经获得了许多荣誉，包括1999年沃尔夫奖、1999年克努斯奖、2001年哥德尔奖和2010年京都奖。

3从计算到数学

Wigderson于1956年出生于以色列海法。阿贝尔奖的表彰认可了他对计算机科学几乎所有领域的贡献，在其中他用可能找到的任何数学工具来解决任何问题，即使对于看似遥远的研究领域也是如此。Sarnak说，Wigderson对他的研究领域的热情具有“传染性”。

到他十几岁的时候，计算机科学家才刚刚开始草拟一个基本的理论框架，这个框架最终贯穿了他的大部分学术生涯。该框架称为复杂性理论，涉及基于算法难以解决的问题对计算问题进行分类。难度的主要衡量标准是计算步骤的数量，最基本的区别是“easy”与“hard”。

一个简单的计算问题的示例是将两个数字相乘。不管数量有多大，计算机都可以迅速找到乘积的。这个问题属于“ P”的复杂度类中，它包含所有易于解决的计算问题。

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

1970年代初期，计算机科学家在计算复杂性领域制定了指导性猜想，询问P中的问题列表是否恰好与NP中的问题相对应，即著名的”P/NP问题“，这也是克雷数学研究所七个千禧年大奖难题之一。

此问题在1977年还很新颖，那时候Wigderson也进入了以色列理工学院。随后几十年里，Wigderson对复杂性理论做出许多基础性的贡献，例如将一些复杂问题进行归类。

回顾过去，Wigderson说：“当我开始读研究生的时候，计算复杂性已经慢慢开始成熟了，在这期间，我自己对问题的认识也加深了”。

在20世纪80年代后期， Wigderson和Ran Raz合作尝试解决计算机复杂性中的完美匹配问题：假设有20台机器，有20个任务待执行，由于每台机器只能完成这些任务的一部分，如何分配机器才能完成所有任务，且每台机器只执行一项任务。

Wigderson 和 Raz提出的解决思路是：加一些限制条件，假设工作在这个问题上的计算机够进行大多数标准的计算运算（如 "与"、 "或"），同时某些运算是被禁止的，例如"非"。

当然，计算机科学家最想证明的是，没有条件约束下，一个计算问题是hard。但到目前为止，他们还没有做到这一点（否则我们就知道P是否等于NP）。因此相反，他们试图证明，当你限制计算资源和可用时间来解决匹配这样的问题时，不存在快速的算法。

Wigderson说：“如果你想找到算法的局限性，当在最一般的情况下无法做到时，就要加以限制，然后将一只胳膊绑在他们的背上。” 在1990年，他和Lovász证明，如果没有数字电路中的逻辑“非”操作，则没有很好的方法并行使用许多计算机来解决电路中的匹配问题。

Wigderson自1999年以来一直在高等研究院进行研究，他在复杂性理论方面取得了许多其他成果，其中包括一种称为之字形乘积的技术，该技术可以直接连接到纯数学的多个领域，并提供了一种走迷宫策略，其中只需要跟踪固定数量的交叉路口。Wigderson的工作广度反映了自他加入以来，计算复杂性领域扩展的方式。

Wigderson最著名的另一项成就是阐明了随机性在计算中的作用。在许多情况下，例如寻找迷宫的出路，基于具有比喻性的硬币翻转现象使算法可以快速找到解决方案。Sarnak说：“如果允许进行随机选择，许多程序的运行速度实际上会快得多。”

Wigderson及其合作者在1990年代发表的两篇论文中证明，在某些假设下，始终可以将快速随机算法转换为快速确定性算法。这从理论上保证了随机算法确实可以找到正确的解决方案。结果确定了被称为“ BPP”的复杂性类与“ P”复杂性类完全相同。它将数十年来对随机算法的研究巧妙地结合到了复杂性理论的主体中，并改变了计算机科学家看待随机算法的方式。

Wigderson的另一项主要工作在信息经济中变得越来越重要。它涉及“零知识证明（zero-knowledge proofs）”，这是一种允许某人在不透露任何有关文件内容信息的情况下验证文件正确性的方法。

本文到此结束，希望对大家有所帮助呢。

 2/2   首页 上一页 1 2