对于图灵奖获得者来说，一切都是计算，有些问题是无法解决的

阿维·维格德森 (Avi Wigderson) 在随机性方面的开创性工作提出了这样的观点：有些问题可能根本无法通过最强大的计算机来解决。

“这是有史以来提出的最基本的智力问题之一，”2024 年 ACM 图灵奖获得者 Avi Wigderson 在谈到 P=NP 问题时说道。 “如果每个人都错了，并且 P 等于 NP，则会产生惊人的后果。”

计算机协会 (ACM) 周三宣布，已授予今年的 A.M.图灵奖通常被称为计算机界的诺贝尔奖，授予新泽西州普林斯顿高等研究院的计算机科学家和数学家阿维·维格德森。 

ACM 表示，威格德森因推进计算理论的基础性贡献而获得认可，特别是在“重塑我们对随机性在计算中的作用的理解”以及“数十年来在理论计算机科学领域的知识领导地位”方面表现突出。

该奖项以英国数学家和计算机科学家艾伦·图灵 (Alan M. Turing) 的名字命名，奖金为 100 万美元，并由 Google 提供资金支持。

该研究所的 Herbert H. Maass 教授 Wigderson 几十年来已经证明了对计算不仅仅是机器的深刻理解。计算是整个宇宙中普遍存在的一种现象。    

“计算是一个非常基本的概念，”Wigderson 在接受 ZDNET 采访时说道。 “这不仅仅是计算机中的算法：一切都会计算。” 

“当你在海滩上看到一个贝壳，有一些显着的图案，这是通过极其简单的步骤计算出来的：它是由一颗颗粒生长出来的，并且在本地，这些颗粒计算出相邻的颗粒，并连接起来——这个非常简单的过程，你进化它，你会得到一些令人惊奇的模式。”

威格德森说，这些简单的局部渐进变化规则“我们非常清楚”，“可以创造非常复杂的现象。”计算示例比比皆是。计算是受精卵如何成为人类的过程，或者是人类细胞在一生中如何分裂的过程。 “还有八卦，”维格德森补充道。 “当你讲述别人告诉你的事情，或者在 Facebook 上告诉你的事情时——信息演变的方式，这些都是计算问题，可以用完整的计算模型来构建。”

将图灵奖授予维格德森尤其合适，因为他的领域，即计算理论，是由图灵于 1936 年通过图灵的里程碑式论文“论可计算数，及其在解决问题中的应用”而开始的。 

图灵为计算的极其广泛的定义奠定了基础，计算是通过局部、增量变化进行的环境演化，其中“环境”可以是人类、星系、海滩上的贝壳、信息或任何数量的现象。 

从图灵的视角来看，正如维格德森及其同事几十年来所提出的那样，每一种自然现象都是计算。维格德森解释说：“白蚁如何建造这些城堡，蜜蜂如何知道去哪里寻找蜂蜜，它们实际上是进化来创造的，尽管它们的脑细胞非常小。”

该奖项特别表彰 Wigderson 在理解随机性在计算中的作用方面做出的贡献。传统计算机，从大型机到 iPhone，都是“确定性的”。也就是说，他们遵循可预测的步骤模式。但自然界中许多最有趣的计算例子都涉及随机性元素，从贝壳到被称为杂音的椋鸟群。  

威格德森和合作者利用对随机性的探索来加深对哪些问题可以和不能“有效”计算的理解。世界上有许多问题——在科学、数学和工程领域——没有已知的有效算法，这意味着可以在“多项式时间”而不是指数时间内运行的算法。

例如，将大整数分解为其质因数并没有可以在小于指数时间内运行的已知算法。但仅仅找到这样的算法还不够；还需要找到这样的算法。计算机科学家和数学家想要以某种方式证明，确切地知道是否可能存在针对此类“难题”的解决方案。 

Wigderson 告诉 ZDNET，ACM 引用的三篇主要论文形成了一个序列，一个进展。 

“问题是算法中的随机性有多强大，”维格德森说。从八十年代开始，计算机科学家已经找到了许多使用随机性作为高效算法的途径，“因此，随机性看起来非常强大。”

“这些作品旨在表明随机性并不那么强大，”他说。相反，Wigderson 和同事开发了伪随机数生成器，可以以有效、确定性的方式解决一些难题。 

“在所有这些论文中，你解决了一个难题，并创建了一个伪随机生成器，它可以确定性地生成看起来随机的位，并且可以替换概率算法中的随机输入[并时尚]确定性算法。”

淘汰随机性，用确定性方法取而代之，最终在使用最复杂的伪随机生成器的论文中达到顶峰。维格德森指出，这一教训表明：“我们可以得出结论，任何多项式时间概率算法都可以成为多项式时间确定性算法。” 

这些发现的一个令人惊讶的副作用是，如果你可以从算法中消除随机性，你就可以证明问题的难度——这是解决问题是否困难的一个引人注目的后门方法。 。 

“不知何故，这两个非常不同的概念（随机性和硬度）密切相关，”维格德森说。 “它们几乎是同一件事。从概率算法中消除随机性，并证明计算问题的难度，是某种对偶问题。”

对于那些希望更深入地研究随机性工作的人，下面列出了这些论文。不过，您可以阅读 Wigderson 的巨著《数学与计算》中有关随机性的章节，该书可免费下载。如果你浏览一下这本书，你就会在下一次鸡尾酒会上领先于大多数人。

• “硬度与随机性”（与 Noam Nisan 合着）
  除其他发现外，本文还介绍了一种新型伪随机生成器，并证明在比之前已知的假设弱得多的假设下，可以对随机算法进行有效的确定性模拟。

• “除非 EXPTIME 有可发布的证明，否则 BPP 具有次指数时间模拟”（与 László Babai、Lance Fortnow 和 Noam Nisan 合着）
  本文使用“硬度放大”来证明有界误差概率多项式时间 (BPP) 可以在较弱的假设下，可以在次指数时间内对无限多个输入长度进行模拟。 

• “P=BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma”（与 Russell Impagliazzo 合着）
  本文介绍了一种更强大的伪随机生成器，具有本质上最佳的硬度与随机性权衡。 

对于 67 岁的威格德森来说，梳理出令人惊讶的联系的乐趣是从小就的一种驱动冲动。 

“我从小就热爱数学，”维格德森说。 “我爸爸对拼图之类的东西很感兴趣。” 

Wigderson 毕业于以色列理工学院，并在普林斯顿大学获得计算机科学硕士和博士学位。去年威格德森获得以色列理工学院荣誉博士学位时，他在获奖感言中动人地讲述了自己的经历。 

“我真的很关心计算模型的形式化，”维格德森在谈到引起他兴趣的东西时说道，“比如，如果某些加密协议是安全的，或者某些算法的运行时间是这样那样的。

“事实上，它涉及这个基本概念，但它实际上是一个数学领域，对我来说非常珍贵。”

威格德森说，他最引以为傲的成就之一是他推进所谓“零知识证明”的工作，即信息可以保密，但两个交易对手仍然可以达成谅解。 “假设我知道一些事情，我知道谁会赢得选举，而你不相信我，而我正在努力说服你[我真的相信]。我有一种方法可以在不告诉你的情况下说服你任何你还不知道的事情。” 

事实上，这种情况是公钥密码学的根源，例如，各方都隐藏自己的私钥，但能够说服对方他们已经权威地签署了一份电子合同。 “这是一个完全矛盾的概念，”维格德森谈到这种零知识证明时说道。 “当你想到这样的事情可能存在时，你会感到震惊。”

威格德森的才智平衡了喜悦与对潜在意义的敏锐感知。例如，哪些问题被证明是困难的问题对社会来说意义重大。 

正如 20 世纪 70 年代所表述的那样，“P=NP 吗？”这个短语询问的是，一个其解可以被验证的问题是否最终也可以通过多项式时间方程来解决——有效地解决。如果是这样，那么很可能会建造一台计算机来在实际的时间内解决世界上一些看似棘手的问题。 

“这是有史以来提出的最基本的智力问题之一，”P=NP 的威格德森说。他个人的猜想是P不等于NP，这也是他所在领域的共识，也就是说，有些问题无法有效解决。

“如果每个人都错了，并且 P 等于 NP，则会产生惊人的后果，”Wigderson 说。 “几乎任何你想解决的问题，你都可以有效地解决——任何事情；你可以治愈癌症。”

然而，“如果 P 不等于 NP，那么对超出我们能力范围的事情的影响是相当重大的，”Wigderson 说。一方面，这意味着人类思维的某些要素，例如创造力，很可能超出计算机的能力范围，因为无法有效地模拟启发法，即人类对艺术创作等事物的感知。 。 

但从另一种意义上来说，玻璃杯是半满的：如果 NP 问题无法有效解决，则意味着密码学——现代经济的全部基础——不会被破解，维格德森指出。

P 是否等于 NP 是一个悬而未决的问题。 “我希望在我有生之年看到有人证明这一点，但现在我对此表示怀疑，”维格德森说。 

量子计算机也不是解决这一僵局的简单方法。 “想象一下量子计算机：这并不存在，”维格德森说。 “我们不知道它是否会存在”——尽管 IBM、谷歌和其他公司对此进行了深入的理论化。 

如果 P=NP 是一个悬而未决的问题，那么当前的问题也是：人工智能（包括“通用人工智能”机器）能做什么或不能做什么来与人类思想同等？当然，宇宙中的一切都可以计算的概念意味着人工智能应该能够达到人类某种程度的能力。 

“我们是碳，而他们是硅，所以材料不同，但困难是在心理层面，而不是操作层面，”维格德森认为。威格德森说，人工智能已经证明它“可以解决许多我们以前不知道如何解决的问题”。他认识“一些著名的数学家，他们开始使用这些设备作为合作者”进行定理证明等。

“对我来说更有趣的是他们不能做什么，”他说。 “这种计算机的局限性是什么？”这些限制之一是针对某些问题训练人工智能模型所需的数据相对较少。 

“例如，设计像相对论或麦克斯韦[麦克斯韦方程组]这样的新数学理论——对于这些来说，例子要少得多，对吗？所以，我认为这种类型的理论突破对于这些机器来说会更困难，因为没有没有那么多数据。”

对于 P 等于或不等于 NP 的许多含义，Wigderson 满足于让新一代引领潮流。

“我和研究所的博士后一起玩得很开心，他们都很聪明，我正在与他们中的一些人合作，并向年轻人学习，”他说。 “在这种情况下，周围都是年轻人，让你不断学习，真是太好了。”