这个问题在1977年还是新奇的，当时维格德森也进入了以色列理工学院 。在随后的几十年里，维格德森对复杂性理论做出了许多基础性的贡献，比如对一些复杂问题进行分类 。
回顾过去 ， 维格德森说，“当我开始读研究生的时候，计算复杂性逐渐开始成熟，在这期间，我自己对问题的理解也加深了” 。
20世纪80年代末，维格德森和冉拉兹合作 ， 试图解决计算机复杂度中的完美匹配问题:假设有20台机器，需要执行20个任务，因为每台机器只能完成这些任务的一部分，如何分配机器来完成所有任务，每台机器只能执行一个任务 。
【2021年数学界 诺贝尔数学奖】维格德森和拉兹提出的解决方案是:增加一些限制，假设处理这个问题的计算机可以执行大多数标准计算(如“与”、“或”) ， 禁止一些操作，如“非” 。
当然，计算机科学家最想证明的是，没有约束 ， 一个计算问题是很难的 。但到目前为止，他们还没有做到这一点(否则，我们将知道p是否等于NP) 。相反，他们试图证明，当你限制计算资源和可用时间来解决匹配问题时，没有快速算法 。
维格德森说:“如果你想找到算法的局限性，当你在最一般的情况下做不到时，你应该限制它，把一只胳膊绑在他们的背上 。”1990年，他和Lovász证明 ， 如果数字电路中没有逻辑“非”运算，就没有好的办法用多台计算机并行解决电路中的匹配问题 。
文章插图
自1999年以来，维格德森一直在高等研究院学习 。他在复杂性理论方面还取得了许多其他成就，包括一项名为“之字形积”的技术，它可以直接连接到纯数学的许多领域 ， 并提供了一种迷宫策略，其中只需要跟踪固定数量的交叉点 。维格德森的工作广度反映了自他加入以来计算复杂性领域的扩展方式 。
维格德森另一个最著名的成就是阐明了随机性在计算中的作用 。在很多情况下，比如找到迷宫的出路，该算法可以基于隐喻性的抛硬币现象快速找到解决方案 。Sarnak说:“如果允许随机选择，许多程序实际上会运行得更快 。”
维格德森及其合作者在20世纪90年代发表的两篇论文中证明了在某些假设下，快速随机算法总是可以转化为快速确定性算法 。这从理论上保证了随机算法能够真正找到正确的解 。结果表明，被称为“BPP”的复杂性类与“P”复杂性类完全相同 。它巧妙地将几十年来对随机算法的研究结合到复杂性理论的主题中，并改变了计算机科学家看待随机算法的方式 。
维格德森的另一项主要任务在信息经济中越来越重要 。它涉及“零知识证明”，这是一种允许某人验证文件的正确性而不泄露其内容的任何信息的方法 。
文章插图
推荐阅读
- 太阳能电伴热费电吗 太阳能电伴热是否费电
- 金针菇炒肉丝
- 大泽乡起义的历史背景，大泽乡起义的领袖人物是谁？
- 我用50首诗词 春天的诗句有哪些
- 去颐和园能坐什么车啊
- 悒郁怎么读，抑郁的读音是什么
- 送老公生日礼物前十件排名榜2021 老公生日送什么礼物
- 记忆力能够通过训练来提高吗
- 鬼泣5什么时候打折 鬼泣5打折时间说明