计算机科学的高塔

2024年4月10日，总部位于纽约市的计算机协会（ACM）宣布，将最新一届图灵奖授予普林斯顿高等研究院教授阿维·维格德森。

图灵奖由计算机协会于1966年设立。该奖以“计算机科学与人工智能之父”，英国计算机学家、数学家阿兰·图灵的名字命名。获奖者必须是在计算机领域具有持久而重大的先进性的贡献。图灵奖是计算机界最负盛名的奖项，被誉为“计算机界诺贝尔奖”。2014年之后，每届图灵奖获奖者可以获得一百万美元的奖金。

在近四十年的研究工作中，维格德森在包括计算复杂性理论、算法与优化、随机性与密码学、并行与分布式计算等在内的理论计算机领域，以及组合学、图论等数学分支中均做出了开创性的工作。这些工作深刻地加强了理论计算机科学与数学和科学之间的联系。

普林斯顿高等研究院教授阿维·维格德森。IAS,Princeton|Dan Komoda|图

因为这些杰出的工作，在获得图灵奖之前，维格德森已经获得了包括内万林纳奖［即现在的国际数学联盟（IMU）算盘奖］、哥德尔奖、高德纳奖、阿贝尔奖、戴克斯特拉分布式计算奖在内的一系列计算机和数学奖项。阿贝尔奖的官方新闻稿对维格德森的工作给出如下评价：“维格德森以善于发现表面上互不相关的学科领域之间的联系而闻名。他加深了数学与计算机科学之间的联系。他对扩大和深化‘复杂性理论’领域的贡献可以说超过了任何其他人。维格德森对复杂性理论中的每一个重大未决问题都进行了研究。在很多方面，这个领域都是围绕着他成长起来的。”计算机协会主席雅尼斯·约安尼迪斯则评价道：“维格德森是理论计算机科学的智力高塔。”

学计算机好找工作

阿维·维格德森1956年出生于以色列海法。他的父母都是纳粹大屠杀的幸存者。维格德森的父亲平夏斯·维格德森在 1939 年纳粹入侵波兰后逃到俄罗斯，并于上世纪五十年代初迁居至以色列海滨城市海法。对小时候的维格德森来说，最大的乐趣就是在家附近的海边游泳和踢足球，以及解谜。

维格德森的父亲平夏斯来以色列时随身携带了一些俄语书籍。这其中就有一些数学谜题的集子。虽然维格德森不懂俄语，但父亲会让他去解这些数学谜题。解开这些书上的谜题，也就成为了维格德森小时候的一大乐趣。这项娱乐活动也激发了维格德森对数学最初的兴趣。中学毕业之后，按照以色列的法律，维格德森服了三年兵役。1977年，维格德森考入了以色列理工学院。出于对数学的喜爱，他最想读的专业就是数学。但是，维格德森的父母希望他能够选择一个更加具有实用性，更加好找工作的专业。作为一名工程师，维格德森的父亲建议道：“既然你喜欢数学，那么就去学计算机专业吧，这样既能学到数学，也更容易找到工作。”

听从了父母建议的维格德森就这样成为了一名计算机专业的学生。以色列理工大学的计算机科学系成立于1969年。在当时，计算机科学还是一门新兴学科，很多在计算机科学系任教的老师都是数学家。他们看到了计算机科学的前景和挑战，并乐于用自己的数学知识和能力来发展这一学科。

这对喜爱数学的维格德森来说，可以说是一个好消息。在大学期间，维格德森同时学习数学和计算机相关的课程，并对算法和复杂性理论产生了浓厚的兴趣。

在当时以色列理工大学的学生当中，有这样一种说法：“如果你足够聪明的话，那你就应该去拿一个博士学位。”因此，在大学毕业之后，维格德森去了美国的普林斯顿大学，跟随计算机科学家理查德·利普顿攻读博士学位。

作为一名计算机科学家，利普顿有着很强的创造力和广泛的兴趣。他会不断地变换研究领域，去研究新的问题。因此，在跟随利普顿学习期间，维格德森也不停地转换研究的问题，去学习新的内容，思考新的问题。这一研究风格也影响了维格德森。实际上，在后来维格德森的研究工作中，他也一直在不停地变换研究的问题和方向，去解决各种难题。

零知识证明

维格德森早期的一项很重要的工作就是对零知识证明的贡献。

零知识证明这一概念最早由莎菲·戈德瓦塞尔、希尔维奥·米卡利和查尔斯·拉克福于1985年提出。这一概念的提出源于这样的思考：在通常的数学证明中，如果张三宣布他证明了某个命题，那么张三需要提供完整的证明过程，来供李四验证。如果李四验证了证明过程没有错误，那么他就可以相信张三的确证明了这个命题。在这个过程中，李四作为验证者，为了验证张三的证明，就需要完整地查看张三的证明过程。而在这个过程中，李四就必然学会了证明这个命题的方法。也就是说，在验证张三的证明是否正确的过程中，李四获得了他原来不曾掌握的信息。

类似的情况也会出现在我们的现今日常生活中，不管是乘坐飞机、高铁，去银行办理业务，还是在网上实名验证个人信息，都需要我们提供足够的信息来“证明”我们是我们自己。而在这个过程中，我们的个人信息就必然会存在着泄露的风险。

零知识证明则提供了另外一种完全不同的解决方法。在零知识证明的体系下，我们在让对方相信“我证明了这个定理”的时候，并不需要向对方提供具体的证明过程。类似的，在我们向对方证明“我就是我”的时候，也不需要向对方提供任何对方事先不知道的额外的个人信息。在这种情况下，自然也就不存在信息泄露的问题。因此，在现在，零知识证明作为一种辅助技术手段，在需要高度信息安全的领域获得了广泛的应用。例如，现在的区块链交易中，就大量使用了零知识证明技术，来保证交易合乎规则。

下面这个经典的“色盲朋友和两个球”的例子，就说明了零知识证明是怎样进行的。

爱丽丝是色盲，鲍勃不是色盲，在鲍勃手上有两个大小、形状完全一样的球，但这两个球的颜色不一样，一个球是绿色的，另一个球是红色的。由于爱丽丝是色盲，所以爱丽丝无法分辨这两个球是否一样，鲍勃需要向爱丽丝证明这两个球是不一样的。在这里，爱丽丝被称为验证者，他需要验证鲍勃的陈述正确与否，鲍勃被称为证明者，他需要证明自己的陈述，即存在两个颜色不一样的球。

按照一般的想法，鲍勃应该告诉爱丽丝，这两个球当中，哪一个是红色的，哪一个是绿色的。但是，这样的话，鲍勃就向爱丽丝提供了她原本不知道的信息，即两个球的颜色。而且，这个信息是作为色盲的爱丽丝无法验证对错的。因此，鲍勃需要在爱丽丝不能获得两个球的颜色的情况下，向爱丽丝证明这两个球的颜色是不一样的这个事实。

具体做法是这样的：爱丽丝当着鲍勃的面拿起两个球，左手拿绿球，右手拿红球。然后将双手放到背后，在背后随机交换左右手上的球，交换完成后爱丽丝将手伸出，并询问鲍勃两个球是否交换过位置。因为鲍勃能看到球上的颜色，每次爱丽丝换过球的位置后，鲍勃都能正确回答爱丽丝的问题。这样经过多次问答之后，爱丽丝就有很大的概率，去相信鲍勃所说的：这两个球的确颜色不一样。

这就是一种最为简单的零知识证明的实例。

通过上面的这个例子，我们很容易感觉到，所谓的零知识证明，往往都会比较繁琐，而且似乎也很难应用到各种复杂的场景当中。但是，1988年，维格德森和他的合作者们证明了一个惊人的结论：对于所有的“可在多项式时间内验证其解是否正确，但不保证能在多项式时间内能找出解的决定性问题”，即所谓的NP问题，都存在一个足够高效的零知识证明。

这项工作在理论上证明了，零知识证明是足够高效的，而且是可以广泛应用的。正如计算机科学家然·拉茨所说的：“这是密码学的一个关键结果，它非常核心，维格德森在密码学方面有一些极其重要的成果，这可能是其中最重要的。”

计算复杂性与随机性

维格德森最为重要的工作，是关于计算复杂性与随机性的。这也是阿贝尔奖和图灵奖的颁奖词中都予以着重提及的内容。

计算复杂性是理论计算机这一学科的核心子领域之一。计算复杂性这一概念的提出，最早可以追溯到上世纪三十年代。在当时，现在意义下的“计算机”还不存在。所谓的“图灵机”，在当时更像是数学家和逻辑学家们的一种纯粹的“智力游戏”。1939年，维特根斯坦在剑桥开设了一门名为《数学基础》的课程。当时刚好在剑桥赋闲的图灵旁听了这门课，并在课上与维特根斯坦进行了深入的讨论。在维特根斯坦与图灵的课堂讨论当中，就有关于证明的复杂性的内容：“一个命题的证明难度和证明的长度有关。”包括维特根斯坦与图灵的课堂讨论在内的内容，被当时听课的维特根斯坦的学生们当做课堂笔记记录留下来。这些笔记后来被结集整理成了《维特根斯坦剑桥数学基础讲义》一书。

后来，随着电子计算机的普及，计算机的运算效率成为了一个具有实际意义的问题。因为对于相同硬件的计算机来说，进行一次运算的时间是相同的。所以计算机解决一个问题所花时间的长短，就直接等同于解决该问题运算次数的多少。这一现实情况在具体应用上，迫使计算机科学家们去发明更具效率的算法。与此同时，在理论研究上，计算复杂性理论也成为了一个相当重要的研究领域。

对于计算机而言，任何一个问题的求解都需要资源。这些资源中最常见的是时间（要通过多少步演算才能解决问题）和空间（在解决问题时需要多少存储器）。计算复杂性理论通过引入数学计算模型来研究这些问题以及定量计算解决问题所需的资源，从而将资源的确定方法正式化。

在计算复杂性理论当中，最为知名的问题就是在1971年，由斯蒂芬·库克和列奥尼德·列文各自独立提出的P/NP问题。

这里所谓的“P”指的是对于这一类的问题，使用确定型图灵机，可以在多项式时间量级（polynomial time class）内，解决该问题。而所谓的“NP”，指的是能够在多项式时间量级内，确定该问题可解，但是不确定是否能够找到具体的多项式时间量级的算法来解决该问题。

P/NP问题指的是，是否所有的NP问题都是P问题。即是否所有可以在多项式时间量级内确定可解的问题，都能够找到具体的多项式时间量级的算法来解决该问题。

2000年，克雷数学研究所将包括P/NP问题、庞加莱猜想、黎曼猜想在内的七个问题列为千禧年大奖难题，悬赏每题100万美元破解这些问题。截止到今天，这七大难题中仅有庞加莱猜想宣告解决。包括P/NP问题在内的其余六个问题仍然没有获得解决。

这里所说的“确定型图灵机”，指的就是通常意义下的图灵机。“确定型”指的是，对计算机输入确定的数据，它会按照事先预设好的算法，给出确定的结果。这看上去似乎是一句废话。在我们的印象中，计算机就应该是这样的。

但是，计算机科学家们发现，如果在算法中引入一定的随机性，就可以在牺牲一点点极轻微的准确性的情况下，大幅提高算法的效率。在很多情况下，带有随机性的算法所带来的效率提升可以达到一个相当惊人的程度。

第二个黄金时代

随机算法所带来的效率提升，使得很多计算机科学家们一度倾向于认为，随机算法可有效求解的问题，要多于确定性算法可有效求解的问题，即P问题。也就是说，在这种意义下，随机算法是强于确定性算法的。

但是，维格德森和他的合作者们的一系列工作，又一次推翻了这种认知。上世纪九十年代，维格德森和他的合作者们先后发表的一系列所谓去随机化论文表明，在一个相当广泛假设条件下，随机算法可有效求解的问题和确定性算法可有效求解的问题，实际上是完全一致的。这意味着高效的随机化算法可以被高效的确定性算法所取代。

维格德森的研究风格，正如姚期智在西蒙斯研究所的访谈中所说的：“推广改进现有的技术，发现更多的联系和应用。”正是这种研究风格，使得维格德森在理论计算机和数学的多个领域内都做出了突破性的工作。他的工作，也在一定程度上改变了我们对于数学和理论计算机，以及我们对这个世界的认知。

正如普林斯顿高等研究院的新闻通稿所说：“维格德森为高等研究院带来了冯诺依曼之后的第二个理论计算的黄金时代。”

来自：南方周末