小乐数学科普：复杂性理论先驱艾维·维格森 Avi Wigderson荣获图灵奖——译自Quanta Magazine量子杂志

Avi Wigderson因其对计算理论的广泛贡献而获得图灵奖，这位多产的研究人员发现了随机性和计算之间的深刻联系，并在职业生涯中影响了密码学家、复杂性研究人员等。

图源：Talia Herman

作者：Stephen Ornes 量子杂志特约撰稿人 2024-4-10

译者：zzllrr小乐（数学科普公众号）2024-4-11

40多年来，Avi Wigderson一直在研究问题。但作为计算复杂性理论学家，他不一定关心这些问题的答案。他常常只是想知道这些问题是否可解，以及如何判断。“这种情况很荒谬，”新泽西州普林斯顿高级研究院的计算机科学家Wigderson说。无论问题看起来多么困难，有效的回答方法都可能隐藏于遥不可及之处。“据目前我们所知，对于每一个我们面临并试图解决的问题，我们不能排除掉有一个可以解决它的算法的可能性。这对我来说是最有趣的问题。”

今天，Wigderson因其对计算理论的基础性贡献，而被评为A.M.图灵奖得主 https://amturing.acm.org ，图灵奖被广泛认为是计算机科学领域的最高荣誉之一。Wigderson的工作几乎涉及该领域的每个子领域。他的同事、合作者和学员表示，他总是能在不同领域之间找到意想不到的桥梁。他从1990年代开始在随机性和计算方面的工作揭示了数学和计算机科学之间的深刻联系，这些联系是当今研究的基础。

荣获2002年Rolf Nevanlinna奈望林纳奖（现称为Abacus算盘奖，参阅 ）的哈佛大学计算机科学家Madhu Sudan（马度·苏丹）表示，Wigderson在该领域的影响不容忽视。“在计算机科学的任何领域，如果不与Avi的工作真正交叉，都是非常困难的，”苏丹说。“在任何地方，你都会发现非常深刻的见解。”例如，在1980年代末，苏丹与Wigderson合作撰写了一篇论文，研究某些数学函数和多项式之间的联系。这项工作开启了苏丹的整个职业生涯。“这对于Avi来说是典型的，”苏丹说。“他进入某个空白领域，提出正确的问题，然后继续前进。”

Wigderson在以色列海法长大，是一名护士和一名电气工程师的三个儿子之一，他们都是二战大屠杀的幸存者。他的父亲喜欢拼图，并对数学的基本思想非常感兴趣，他与孩子们分享了这些基本思想。“他就是让我被这种‘病毒’感染的人，”Wigderson说。1970年代，当他在海法理工学院开始上大学时，他想主修数学，但他的父母却引导他选择了计算机科学。“他们认为我毕业后能找到一份工作也许是个好主意，”他说。

Wigderson坐在加州大学伯克利分校的图书馆里

图源：Talia Herman

他发现这个领域充满了深刻的、尚未解答的数学问题。他最早的开创性努力之一集中在一个看似矛盾的问题上：是否有可能让其他人相信一个数学命题已被证明正确而不展示如何证明它。

普林斯顿大学计算机科学家Ran Raz（兰·拉兹）表示：“看到证明的人不会知道证明本身的任何信息。”1985年，Shafi Goldwasser、Silvio Micali和Charles Rackoff引入了零知识交互式证明（zero-knowledge interactive proof）的概念 https://dl.acm.org/doi/10.1145/22145.22178 ，演示了其在一些命题中的用途。Wigderson与Micali和Oded Goldreich后来阐述了这个想法，列出了条件，证明如果一个命题可以被证明，它也有一个零知识证明。

“这是密码学的一个关键结果；极其核心，”拉兹说。使用零知识证明，某人可以证明他们使用自己的密钥正确加密或签署了消息，而无需透露任何相关内容信息。“Avi在密码学方面有一些极其重要的成果，这可能是其中最重要的。”

尽管Wigderson对计算机科学的各个领域都做出了贡献，但他将随机性与难题联系起来的工作可能是他最重要的

图源：Talia Herman

但也许Wigderson最基本的结果在于另一个领域：将计算难度与随机性联系起来。到1970年代末，计算机科学家已经意识到，对于许多难题，采用随机性的算法（也称为概率算法 probabilistic algorithm）可以远远胜过其确定性替代方案。例如，在1977年的证明 https://epubs.siam.org/doi/10.1137/0206006 中，Robert Solovay和Volker Strassen 引入了一种随机算法，可以比当时最好的确定性算法更快地确定一个数字是否为素数。

对于某些问题，概率算法可以指向确定性算法。1980年代初，Wigderson与加州大学伯克利分校的Richard Karp（理查德·卡普）合作，将随机性的概念与计算困难的问题联系起来，这意味着没有已知的确定性算法可以在合理的时间内解决这些问题。“我们不知道如何证明它们很困难，”Wigderson说。然而，他和卡普发现了一种针对某个难题的随机算法，后来他们能够将其去随机化，从而有效地揭示了它的确定性算法。大约在同一时间，其他研究人员展示了密码学问题中的计算难度的假设如何能够实现一般的去随机化。

随机性的不合理的有效性促使他思考随机性本身的本质。他和当时的其他研究人员一样，质疑它对于有效解决问题的必要性以及在什么条件下可以完全消除它。“最初，并不清楚这是否只因我们自己的愚蠢，而无法消除随机性，”他说。“但更大的问题是随机性是否总能有效消除。”他意识到对随机性的需求与问题的计算难度密切相关。

在1994年的一篇论文 https://www.sciencedirect.com/science/article/pii/S0022000005800431 中，他和计算机科学家Noam Nisa阐明了这种联系。他们证明，如果存在任何自然难题，正如大多数计算机科学家所怀疑的那样，那么每一种有效的随机算法都可以被有效的确定性算法所取代。“你总是可以消除随机性，”Wigderson说。

对Wigderson来说，现在总是研究计算复杂性的好时机。“这片新天地刚刚绽放，非常美丽。”

图源：Talia Herman

重要的是，他们发现确定性算法可能使用“伪随机”（pseudorandom）序列——看似随机但实际上并非随机的数据串。他们还展示了怎样使用任何难题来构建伪随机生成器。将伪随机位（而不是随机位）输入概率算法将为同一问题产生有效的确定性算法。

苏丹表示，这篇论文帮助计算机科学家认识到随机性的程度，这有助于揭示难题的复杂性以及如何解决它们。“这不仅仅是随机性，还有对随机性的看法，”他说。“这就是关键所在。”

苏丹指出，随机性似乎无处不在，但事实上却很难找到。“人们告诉你，圆周率的数字看起来是随机的，或者素数的数字序列看起来是随机的，”他说。“它们是完全确定的，但对我们来说它们似乎是随机的。”他说，对随机性的感知是当今计算机科学的核心。“这就是Avi大力提倡的事情。”

随机性已成为复杂性理论中的强大资源，但它却难以捉摸。Wigderson指出，抛硬币和掷骰子并不是真正随机的：如果你有足够的关于物理系统的信息，那么结果是完全可以预测的。他说，完美的随机性是难以捉摸且难以验证的。

但对于Wigderson来说，计算的例子无处不在——不仅在智能手机、笔记本电脑和加密算法中，而且在生物和物理系统中。近几十年来，计算理论的研究成果让人们对一系列意想不到的问题有了深入的了解，例如从鸟群和选举结果到人体内的生化反应。“基本上，任何自然过程都是一种进化，你可以将其视为计算，因此你可以这样研究它。几乎所有事情都需要计算。”

参考资料

https://www.quantamagazine.org/avi-wigderson-complexity-theory-pioneer-wins-turing-award-20240410/

https://amturing.acm.org

https://dl.acm.org/doi/10.1145/22145.22178

https://epubs.siam.org/doi/10.1137/0206006

https://www.sciencedirect.com/science/article/pii/S0022000005800431

·开放 · 友好 · 多元 · 普适 · 守拙·

让数学

更加

易学易练

易教易研

易赏易玩

易见易得

易传易及

欢迎评论、点赞、在看、在听

收藏、分享、转载、投稿

查看原始文章出处

点击zzllrr小乐

公众号主页

右上角

数学科普不迷路！