图灵奖得主Avi Wigderson：P vs NP、零知识证明、量子计算，分别意味着是什么？ 原创

写一篇自己也不完全懂的笔记。虽然不完全懂，但看完确实有收获，懂的人应该能收获更多。

Avi Wigderson是人类历史上唯一同时获得图灵奖（2023年，计算机科学最高荣誉）和阿贝尔奖（2021年，与László Lovász共享，数学领域最高荣誉之一）的学者。他是普林斯顿高等研究院IAS数学学院的Herbert H. Maass教授，研究领域覆盖计算复杂性、随机性理论、密码学、图论和量子计算。

笔记来自软件工程师Ryan Peterman主持的播客，2026年6月1日上线，时长接近两个半小时。

为了便于理解，我整理了一条贯穿全场的主线，一句话总结就是：困难不只是障碍，困难本身是资源。NP完全问题极难求解（第一章），但正因为它们难，答案对算力有限的观察者来说就像随机的，可以被当作伪随机比特来用（第三章）。同样是因为困难问题存在，现代密码学和零知识证明才有地基可以站（第四章）。量子计算威胁了其中一部分困难问题，所以需要找到连量子计算机都攻不破的新困难问题来重建地基（第五章）。

另有两个旁支。第二章讲的是计算资源之间的意外关系：时间和空间看起来差不多大，结果空间可以比时间小得多，50年的认知在2025年被推翻。第六章讲的是做这种研究的人怎么过日子：蚁群式协作、大多数日子一无所获、建模比解题重要。

最后Wigderson被问什么人适合做理论研究，他说：你早上出门，晚上回来，什么也没做成。你想做的事没有进展，想了一天，什么也没想通。可是，如果你不享受这个过程本身，这个领域可能不适合你。

一、P vs NP：一个关于人类能知道多少的问题

1、NP和P：验证容易，求解未必容易

计算理论会把问题按解题所需的资源多少分成不同的类别，叫复杂性类。NP就是其中一个。NP的定义是：如果有人给出一个答案，我们能高效地验证它是否正确，这个问题就属于NP。

为什么说NP覆盖了人类想解决的一切问题？因为不管是数学家寻找定理证明、科学家构建理论、工程师设计满足约束的桥梁、侦探破案，这些活动都有一个共同前提：你至少得知道，找到答案的时候能认出它是答案。如果连这一点都做不到，那这件事根本不算一个你"真的想解决"的问题。

P也是一个复杂性类。如果存在一个算法，不需要任何人给提示，自己就能在合理时间内直接算出答案，这个问题就属于P。手机上的导航app能算出任意两点之间的最短路径，不需要有人先告诉你走哪条路，算法自己能找到，所以最短路径问题属于P。

NP和P的区别在于：NP只要求你拿到答案后能判断对不对，P要求你自己就能把答案算出来。这两个类是否相等，是计算理论中最大的未解问题，叫P vs NP问题。P vs NP是问题的名字，P = NP和P ≠ NP是两个可能的答案。

如果P = NP，意味着能验证就一定能求解，人类想知道的一切，从癌症的治愈方案到任何数学猜想的证明，只要答案存在且可验证，就一定能被算法找到。如果P ≠ NP，意味着存在一些问题，答案可以被快速验证，但永远不可能被快速算出来。

2、所有NP问题背后是同一套逻辑

旅行商问题（找经过所有城市的最短路线）、数独、图着色（给地图着色让相邻区域颜色不同）、布尔可满足性问题，这些看起来完全不同。布尔可满足性这个名字拆开看："布尔"是说每个变量只能取真或假两个值，"可满足"是问能不能找到一组赋值让所有条件同时成立。比如有三个条件"A或B为真""B或C为真""A和C不能同时为真"，能不能给A、B、C各指定真或假，让三个条件全部满足？这就是一个布尔可满足性问题。但它们有一个共同点：验证答案是否正确的过程，都是计算机上一步一步的局部操作。

什么叫局部操作？不管什么计算设备，它每一步做的事都只涉及少数几个比特：看这两个数，加一下；看这个条件，判断真假。把一次验证计算的所有步骤摊开成一张表，每个格子的状态只取决于它旁边的几个格子。这种"每个格子都必须和邻居一致"的要求，天然就是一组逻辑约束：给每个格子填一个值，使得所有相邻格子之间的关系同时成立。

这意味着：任何NP问题的验证过程，不管表面上是在验证路线、验证着色还是验证蛋白质构型，都可以被翻译成一组逻辑约束，也就是一个布尔可满足性问题。以分解整数为例：有人给你两个因子，你做一次乘法验证它们的乘积是否等于原来的数。乘法就是一系列局部操作（逐位相乘再进位），每一步只涉及几个数位。这些操作可以被写成一组逻辑约束，所以"验证因子是否正确"可以被翻译成一个可满足性问题。

3、NP完全问题：攻破一个就攻破全部

上面这个事实有一个惊人的后果。既然任何NP问题都可以被翻译成一个可满足性问题，那如果你有一个高效的可满足性求解器，你就自动能高效求解所有NP问题。比如你要解一个旅行商问题：第一步，把城市、距离、约束条件按固定规则转换成一组布尔变量和逻辑条件；第二步，交给可满足性求解器，它给你一组真假赋值；第三步，按同样的规则把这组赋值读回一条路线。你拿到的就是旅行商问题的解。

可满足性问题不是唯一有这种"万能翻译器"地位的问题。数独、旅行商、图着色也都有。假设你是一个数独高手，任意尺寸的数独都难不倒你。有人拿来一个旅行商问题（10个城市，找最短路线），你不会解。但存在一套固定的机械步骤，能把任何旅行商问题变成一道数独题，而且从数独的解可以反推出最短路线。如果你真能高效解任意数独，你就自动能高效解任意旅行商问题。

这类能充当万能翻译器的问题叫NP完全问题。NP完全是贴在具体计算任务上的分类标签：旅行商、数独、可满足性各自是一个问题，"它是NP完全的"是数学家对这个问题做出的判定，意思是已经证明了它具有万能翻译器的性质。所有被判定为NP完全的问题难度完全相同：攻破一个就等于攻破全部。目前已知的NP完全问题有几千个，分布在数学、物理、生物、工程、经济学各个领域。解不出来怎么知道有几千个？因为判定一个问题有多难和解决这个问题是两件事，就像你可以证明一块巨石搬不动，不需要真的搬动它。过去五六十年里，成千上万的研究者拼命想攻破哪怕一个，没有人成功过。这是大多数理论计算机科学家相信P ≠ NP的最强理由。

但Wigderson话锋一转：这些全是直觉，不是证明。如果明天真有人想出全新的思路，找到了NP完全问题的高效算法，我们这些直觉一个也不算数。

4、理论上无解不等于实际中无解

前面说NP完全问题50年没人攻破。是不是碰到这类问题就彻底没办法了？

不一定。NP完全说的是最坏情况：在所有可能的输入里，存在某些极端的输入，任何算法都没法快速搞定。但你实际碰到的输入未必是那些极端的。类比一下：数独是NP完全问题（任意尺寸的），但你每天做的报纸上的9×9数独总是能解的，因为出题人选的是有解且不太难的题目，你从来不会碰到理论上最坏的那些。

蛋白质折叠是同样的道理。蛋白质是一条氨基酸链，合成之后会自动折叠成能量最低的三维形状。一条几百个氨基酸的链，可能的折叠方式比宇宙中的原子还多，从中找到能量最低的那个构型，这个问题被证明至少和NP完全问题一样难（计算理论把这类问题叫NP难问题）。那人体折叠蛋白质，是在解这个NP难题吗？不是。人体只需要折叠进化选中的那几万种蛋白质，就像你只做报纸上的数独，不做理论上最难的那些。进化筛选出了容易折叠的蛋白质，偏偏没选中那些让算法崩溃的链。

5、PCP定理：连近似解都不行

NP完全问题的精确解太难找。自然的退路是：我不追求满足所有条件了，能不能满足尽可能多的条件？比如一个布尔可满足性问题有1000个条件，满足全部太难，能不能找到一组赋值满足其中950个？这就是近似解的思路。

先看一个基准。回到前面说的布尔可满足性问题，假设每个条件涉及三个变量，形式都是"这三个变量中至少有一个为真"。你什么都不看，随机给每个变量抛硬币决定真假。每个条件被违反的唯一情况是三个变量恰好全是假，概率是1/2 × 1/2 × 1/2 = 1/8。所以每个条件被满足的概率是7/8，也就是87.5%。闭着眼睛猜，不用任何算法，就能满足87.5%的条件。

PCP定理的一个推论（由复杂性理论家Håstad加强）说的是：想比随机猜好哪怕一丁点，比如满足87.6%的条件而不是87.5%，这件事的难度就跟找到满足所有条件的精确解一模一样，都是NP完全级别的。随机猜的87.5%是免费的天花板，想多迈一步就撞上NP完全的硬墙。连近似都没有捷径。

到这里，第一章讲的都是哪些问题难、有多难、连近似都不行。接下来暂时离开这条线，看看计算资源之间的一个意外关系：时间和空间看起来差不多大，其实不是。

二、时间和空间的隐秘关系：50年老墙被推倒

1、Ryan Williams 2025年的突破：时间t的计算只需要√t的空间

时间和空间是计算中两种最基本的资源。时间是执行步数，空间是计算过程中需要的存储单元数。两者有一个显然的关系：一次计算执行了多少步，最多就用多少个存储单元，因为每一步最多访问一个新单元。空间不会超过时间。

1975年，Hopcroft、Paul和Valiant三位计算理论家把这个上界改进了一点点：空间可以从t压缩到 t / log t。拿100万步的计算来说，原来上界是100万个存储单元，他们压缩到了大约5万个。这个结果50年没人打破，而且在某些受限计算模型里被证明是最优的。

2025年2月，MIT的Ryan Williams证明：对于多带图灵机（理论计算机科学中建模通用计算的标准机器），空间上界可以压缩到大约√t。还是100万步的例子，从5万个存储单元降到1000个。代价是运行时间会大幅膨胀，但这个结果说明空间可以比时间小得多，两者的关系远不是"差不多大"这么简单。

Williams的证明建立在James Cook（NP完全性理论创始人Steve Cook的儿子）和Ian Mertz的一个早期结果之上。

2、Barrington定理：用常数空间完成任意长度的计数

Wigderson讲了一个他第一次听说时完全不信的结果：如果你有一串比特想判断0多还是1多，也就是计算理论里所说的多数表决问题，计数到n需要log n个比特来存储（比如计数到1000需要10个比特，因为2的10次方是1024），这看起来就是下界。但David Barrington在1980年代发现，如果你可以随机访问输入中的任何一个比特（意思是可以直接跳到第17个或第8100个，不用从头往后读），仅用常数空间，比如5个比特，就能完成任意长度输入的多数表决判断。不管输入有一千个比特还是一万亿个，5个比特的工作记忆就够了。

这个结果的核心工具是非交换代数，也就是操作的顺序会影响结果的数学结构。具体做法是：看到1就做旋转，看到0就做翻转，这两个操作作用在五个元素的排列上，先旋转后翻转和先翻转后旋转得到不同的结果。通过精心编排这些操作的顺序，你可以用一种叫"交换子"的操作组合（先做A再做B再撤销A再撤销B）来模拟逻辑AND运算。最终，一个布尔公式的计算被编码在五个点的排列状态里，只需要常数个比特就能记住。

他第一次听到这个结论时还是博士后，第一反应是"不可能"。但这个结果在密码学里有重要用途，而且时间开销仅为平方级，实际可用。

Wigderson还用了一个直觉谜题来解释这种非交换操作为何能编码计算：你有一幅画，想用绳子挂在墙上的两颗钉子上。两颗钉子都在时画挂着；拔掉任何一颗，画就掉到地上。怎么绕绳子才能做到？两颗钉子都需要才能挂住，这正好就是一个逻辑AND（两个条件同时为真才输出真），而它的解法就需要利用"绕了再反绕"的非交换操作。

回到主线。第一章把困难问题当障碍看：NP完全问题50年没人攻破，连近似都不行。但Wigderson获图灵奖的核心贡献恰恰是翻转这个视角：困难问题不只是障碍，它本身是一种可以被利用的资源。逻辑是这样的：如果一个问题的答案连最强的多项式时间算法都猜不出来，那这个答案对这些算法来说就像随机的。"看起来随机"不是一个缺陷，而是可以被拿来当伪随机比特用的材料。这就是第三章的起点。

三、随机性是观察者的函数

1、随机性的质量取决于谁在看：抛硬币的三个实验

Wigderson引用了密码学先驱Blum和Micali论文中的一个思想实验。同一枚硬币从手指弹出，三种情况下你猜正反面的成功率完全不同。

第一种情况，你裸眼看，成功率1/2，这就是经典的随机事件。第二种情况，你面前有一台笔记本电脑，但硬币一秒就落地，来不及计算，成功率还是约1/2。第三种情况，你的电脑连着一台Cray超级计算机，超算连着一堆对准硬币的传感器和相机，能在硬币离开手指的瞬间测量所有角动量、空气湿度、距离等参数，在硬币落地前算出结果。成功率接近100%。

三个实验里，硬币抛掷本身没有任何变化。变的只有观察者的计算能力。传统定义把随机性当作事件本身的属性，复杂性理论的定义则聚焦于观察者：对你来说有多少熵（不确定性），取决于你能调动多少计算资源来预测。同一个事件，对弱观察者是随机的，对强观察者是确定的。

但这个原则有边界。Wigderson引用了Shannon定理：如果你要生成密码或密钥，密码的安全性等于其中的真实熵。这时候你需要的是信息论意义上的真随机，不是"对某个算法来说看起来随机"。生成一个真随机比特就是生成一个真随机比特，你的计算能力再强也替代不了这个需求。

2、硬度 = 随机性：一个看似不相关的等价关系

如果你面对一个NP难问题的实例，作为一个多项式时间算法（运行步数是输入长度的某个多项式倍数，比如n²或n³，而不是2的n次方），你猜不出答案。答案对你来说就有熵。这就是"困难问题蕴含随机性"的起点：既然你算不出来，那个答案对你来说就像随机的。

但这只是起点。原始的熵可能极小，也许只有极微弱的不确定性。要变成有用的伪随机生成器，需要做两件事：先放大硬度（把"1%的输入猜不对"变成"50%的输入猜不对"），让随机实例的答案对多项式时间观察者来说接近50/50；再从少量真随机种子扩展出大量伪随机比特。

Wigderson和Nisan设计了一种叫NW生成器的装置来完成后半段工作。它的原理可以这样理解：你有一个连多项式时间算法都算不出的困难函数，你只需要一小段真随机种子（比如10个比特），从中按照不同的规则挑出若干子集（比如挑出第1、3、7号比特作为一组，第2、5、8号作为另一组），把每组喂给困难函数得到一个输出位。因为函数对多项式时间算法来说不可预测，每个输出位对它来说都像随机的。虽然这些输出位之间其实高度相关（它们共享种子），但没有高效算法能检测到这种相关性。这样你就从10个真随机比特"膨胀"出了远多于10个的伪随机比特。

最终结论：如果存在某个问题确实需要天文数字级别的计算资源才能解决（这个假设比P ≠ NP更强但被广泛相信），那么P = BPP成立，即任何高效的概率算法都有等效的高效确定性算法。换句话说，抛硬币不会让算法变得更强。随机性在算法中的力量，可能没有我们曾以为的那么大。

3、从概率到确定性的完整故事：素数判定

素数判定这个问题，高斯在几百年前就想要一个高效的判定方法，但长期没有人找到。1970年代，Solovay-Strassen和Miller-Rabin分别发明了概率性素数测试：给一个数，算法靠抛硬币做随机抽查，如果通过了多轮抽查就报告"极大概率是素数"，如果某轮没通过就确定"不是素数"。速度快，但依赖完美随机比特。人们开始追问：能不能用更少的、有结构的随机性来替代？

没有人在这两个算法上找到好答案。但2000年代初，印度计算机科学家Agrawal、Kayal和Saxena换了一条路，设计了一个不同的概率素数测试。因为新测试对随机性的使用方式不同，分析之后发现它其实不需要所有比特完全独立，结构化的伪随机就够用，最终用数论工具从少量比特生成了足够的伪随机序列，得到了确定性算法。

这个故事展示了一条路径：有时候去随机化的关键不是优化现有算法，而是设计一个新算法，使得对随机性的依赖方式更容易被分析和替换。

4、随机性纯化：从噪声中提炼出真随机

现实世界的随机源都不完美。天气、股价、量子现象，这些都无法精确预测，但也不是完美随机的：天气有自相关，股价有趋势，采样总有偏差。

随机性提取理论要解决的问题是：给你一堆不完美的随机比特，能不能从中提炼出接近完美的随机比特？

直接提取单个完美串是不可能的，因为你不知道熵藏在哪些比特里，没法只挑好的。但可以生成大量候选串（比如几千个），每个长度和原始数据中的真实不确定性大致相当，其中99%是真正的完美随机。剩下1%是坏的，你不知道哪些坏。但这已经够用了，把你的概率算法在每个候选串上跑一遍，取多数投票，坏串的影响会被淹没。

在多源提取的场景中，如果你有多个互不相关的弱随机源，一个关键工具来自算术组合学中的和积定理。这个定理说的是：对任意一组K个整数，要么把它们两两相加能得到远多于K个不同的和，要么把它们两两相乘能得到远多于K个不同的积。至少有一种操作能让集合急剧膨胀。加法和乘法在这个意义上是"正交"的，一种不膨胀，另一种必定膨胀。利用这个性质，把几个弱随机源的输出当成数字做混合运算，就能让输出的不确定性（熵）超过任何单个输入源，逐步逼近完美随机。

困难问题能变成随机性的来源。同样的逻辑还能走得更远：如果某些计算确实很难倒着做（比如把两个大素数乘起来容易，把乘积分解回去极难），那就可以在此基础上构建密码系统和证明系统，让人在不泄露秘密的前提下证明自己拥有秘密。这就是零知识证明的基础，也是Wigderson最著名的贡献之一。

四、零知识证明：什么都不泄露，但让你完全信服

Wigderson是零知识证明领域的奠基人之一。1985年，现代密码学的奠基者Goldwasser、Micali和Rackoff三人定义了交互式证明和零知识的概念；1986年Wigderson与Goldreich、Micali一起证明了零知识证明的普遍性定理。Goldwasser和Micali后来因为密码学的奠基性贡献获得了2012年图灵奖。

1、零知识的含义：比"不泄露密码"深刻得多

前面说NP问题的特点是答案可以被高效验证。换一种说法：有人声称有答案（证明者），把答案写下来（证明），你检查一遍（验证者）。这就是一个证明系统。经典的NP证明是单向的：证明者写完，验证者读完，结束。交互式证明把这个过程变成对话：证明者和验证者可以来回提问和回答，验证者可以抛硬币做随机挑战，最终以极高概率确信证明者的声明为真。

零知识在交互式证明的基础上加了一个要求：验证者从整个交互中获得的信息，除了"命题为真"这一事实之外，绝对为零。

Wigderson说，这听起来荒谬透顶。想象有人说证明了P ≠ NP，你跟他交互之后完全相信他确实证明了，但你对证明方法一无所知。怎么可能有人让你相信他证明了P ≠ NP，而你结束对话时对证明方式一无所知，只知道对方确实做到了？

2、图着色协议：零知识如何运作

Wigderson用三着色问题演示了零知识证明的核心思路。证明者声称能用三种颜色为一张图着色，使得每条边的两个端点颜色不同。

协议流程：证明者对每个顶点的颜色做一个密码学承诺，效果类似把颜色放进密封信封。验证者随机选一条边，证明者打开这条边两端的承诺。验证者检查两个颜色是否合法且不同。重复多轮。

正确性容易理解：如果图不是三可着色的，无论证明者怎么承诺，至少有一条边是错的，验证者有非零概率选中它。重复几千轮，作弊者逃脱的概率指数级趋近于零。

零知识性的关键在于：证明者每轮都随机把红绿蓝三种颜色重新洗牌，比如这轮红变绿、绿变蓝、蓝变红，下轮又换一种排列，一共有六种排列方式。在这种均匀随机的颜色洗牌下，验证者看到的任何一条边的两个颜色，都只是"两个不同的随机颜色"。验证者自己随机抽两个不同颜色就能得到同样的分布。每轮学到的信息量为零。

3、从图着色到一切：NP完全性再次登场

三着色是NP完全问题。通过归约（前面说的"问题翻译"），任何NP命题都能被转换成一个三着色问题的实例。而且归约不仅保持命题的真假，还保持证明的可翻译性：如果你有原问题的证明，就能构造出对应图的合法三着色方案。

所以，任何可以被数学证明的命题，都有零知识交互式证明。密码学、区块链、隐私计算中大量使用的零知识技术，根基就在这里。

Wigderson坦言他当年预言零知识证明永远不会被工程实现，因为先把问题归约到图着色再走协议的开销太大。结果他错了。工程师们找到了更直接的方案，在更强或不同的假设下大幅简化了协议。

2025年7月，IAS博士后Rahul Ilango发表了一项成果。前面讲的图着色协议需要证明者和验证者反复对话好几千轮，还需要双方事先共享一些公共参数（叫可信设置）。Ilango利用哥德尔不完备性定理的思想（存在真但不可证的命题），构造出了一种零知识证明系统：证明者只需要发送一条消息，验证者独立检查就行，不需要对话；也不需要任何事先约定的公共参数；而且如果命题为假，根本不可能存在能骗过验证者的假证明。

第三章和第四章的一切，从伪随机生成器到零知识证明到整个公钥密码体系，都建立在一个假设上：某些问题确实很难解。如果这个假设被推翻，地基就没了。量子计算正是对这个假设最大的威胁。

五、量子计算到底改变了什么

1、Shor算法的冲击波还在扩散

1994年，MIT数学家Peter Shor发现了高效的量子整数分解和离散对数算法（离散对数是和分解整数类似的另一类数学难题），直接威胁了当时（也是目前）几乎所有公钥密码体系的安全基础。公钥密码是让两个从没见面的人也能安全通信的技术基础，银行转账、HTTPS网页、电子签名都靠它。自Shor算法发现以来，各国政府和企业投入了数十亿资金建设量子计算的技术基础设施。

在硬件层面，量子比特需要保持在叠加态才能做量子计算，这种状态叫相干性，极其脆弱。经典计算机的硬件错误率低到基本可以忽略，Intel芯片甚至不需要内置纠错。量子系统则不同，量子力学里"一切影响一切"，外界噪声会不断干扰计算，量子纠错码只是解决方案的一部分。

Wigderson说，别说量子计算机了，如果明天有人找到一个经典的多项式时间分解算法，全世界就会陷入混乱，因为几乎所有安全系统的基础假设会同时崩溃。

2、后量子密码学：重建安全的地基

因为Shor算法的存在，密码学界需要找到即使面对量子计算机也无法高效攻破的数学难题。要构建公钥系统，需要一种特殊的单向函数叫陷门函数：正着算容易，倒着算极难，但持有一把"密钥"（陷门）的人可以倒着算。这种函数本身就稀缺。已知的只有分解整数、离散对数，以及1990年代匈牙利计算机科学家Ajtai基于格问题提出的方案及其衍生变体。格问题是一类高维空间中的几何难题，比如在一个由规则排列的点构成的无限点阵（格）中，找到离原点最近的那个点。

Shor算法之所以有效，核心在于它把分解和离散对数问题归约为周期查找问题，而量子计算机可以同时处理所有可能的输入（叠加态），然后用一种叫量子傅里叶变换的操作让正确答案的信号互相增强、错误答案的信号互相抵消，从而高效地找到周期。但格问题至今没有人找到高效的量子算法。NSA等机构正在推动全球向抗量子密码迁移。

3、MIP* = RE：复杂性理论产出了物理学和数学的定理

大约在2020年初，Ji、Natarajan、Vidick、Wright和Yuen五位来自悉尼科技大学、加州理工和多伦多大学的研究者证明了一件事：如果证明系统中有多个量子证明者（他们之间有量子纠缠），那么一个高效的经典验证者能够验证的问题范围，包括了停机问题这种根本不可计算的问题。停机问题就是判断一段给定的程序到底会在有限步内停下来还是永远跑下去，图灵在1936年证明了不存在能解决所有情况的通用算法。计算理论把这个结论记为MIP* = RE。

Wigderson承认这听起来像是复杂性理论家在沙盘里堆城堡。但这篇约165页的论文立刻解决了数学和物理中多个悬了几十年的猜想，包括纯数学中的Connes嵌入猜想和量子物理中的Tsirelson问题。搞复杂性理论的人造出的工具，解决了数学家和物理学家用自己的方法长期解决不了的问题。而且这只是开始，基于同样技术的后续论文正在解决更多数学猜想。

从P vs NP到量子计算，Wigderson的职业生涯跨越了计算理论最核心的几个问题。播客的最后，他聊了聊做这种研究是什么体验。

六、做理论研究的人怎么过日子

1、科学进展是蚁群协作，大突破罕见且不可预期

Wigderson把科学研究比作蚁群工程。每年的理论计算机科学会议上有几百篇论文，绝大多数，包括他自己的绝大多数论文，都是在某个方向上做一点增量推进：改进一个界、发现一个技巧的变体、证明一个中等规模的定理。这些增量是必要的基础设施。

偶尔有人发现一个根本性的新洞察，冲击波传遍整个领域。但你不能为了大突破而工作。做这些问题不是为了百万美元奖金，百万美元对这些问题来说根本不算什么。

2、理论计算机科学最核心的活动是建模

比起"解题"，Wigderson更强调"建模"的重要性。解题是在已有的框架里工作：问题已经定义好了，你去证明或者找答案。建模是创造框架本身：在你建模之前，用来表述问题的概念还不存在。前面提到的好几个突破都是建模贡献：Cook和Levin不是解了一道题，而是创造了NP完全性这个分类框架，让几千个看似无关的问题被识别为同一难度；Goldwasser和Micali不是证了一个定理，而是发明了"交互式证明"这个模型，零知识证明才有了可能。

他拿随机性举例：传统定义聚焦于事件本身是否随机，复杂性理论的定义聚焦于观察者的计算能力。这不是在旧定义下解了一道题，是把"随机"这个词的意思换了，然后一整个新领域（伪随机性、去随机化）从新定义里长出来了。定义一个好的概念，比在旧概念里证一个新定理，影响范围大得多。

3、给年轻研究者的建议：在早期阶段做你最享受的事

Wigderson说他不太有资格给建议，因为他主要是运气好：好导师、好合作者、好社区。但他强调一点：在职业生涯初期发现自己的研究品味比追逐热门问题更重要。读不同领域的论文，尝试不同类型的问题。往往你最喜欢做的事，就是你最擅长的事。

他讲了一个细节：第一次参加理论计算机科学会议时他还是一年级博士生，有人把他介绍给NP完全性理论的奠基人之一Richard Karp，他说自己证明了某个问题是NP完全的，Karp真的对他的工作有兴趣，认真问了细节。这个领域没有等级壁垒，年轻人可以直接和大牛对话。

他对理论研究者的日常体验也坦诚：大多数日子，你早上出门，晚上回来，什么也没做成。他说的那段话放在了本文开头。

总结

P vs NP是关于人类知识边界的哲学命题，但它有精确的数学表述和具体的工程后果。随机性不是事物的属性，而是观察者与事物之间关系的属性，但这个哲学洞察直接通向可证明的去随机化定理。零知识证明听起来像逻辑悖论，但它有严格的协议、可量化的安全保证和已经在链上运行的实现。

对于关注AI和计算前沿的读者：第一，后量子密码迁移不是远期问题，如果明天有人找到经典分解算法（不需要量子计算机），现有安全体系立刻崩塌。第二，复杂性理论在过去五年里（MIP* = RE、Ryan Williams的时空定理、Ilango的零知识突破）产出了一连串将理论边界大幅推移的结果，这些结果对密码学、安全系统、甚至物理学基础问题都有实质性影响。

核心归纳

Q1: P vs NP到底在问什么？NP是所有"答案可以被高效验证"的问题，直觉上对应人类真正想解决的一切问题。P是已经能被高效求解的子集。P vs NP问的是：验证的容易是否蕴含求解的容易？如果P = NP，人类想知道的一切（只要答案存在且可验证）都能被算法找到。几乎所有理论计算机科学家认为P ≠ NP，但50年来没有人能证明这一点。

Q2: 随机性在算法中真的有用吗？有用但可能没那么有用。在"困难问题确实存在"的假设下（比P ≠ NP稍强），任何高效概率算法都有等效的高效确定性算法（P = BPP）。核心洞察是随机性的质量取决于观察者的计算能力，对多项式时间算法来说"看起来随机"的序列不需要真的随机，只要没有算法能分辨真假即可。但这有边界：密码学中需要信息论安全的场景仍然依赖真随机。"硬度等价于随机性"的范式是Wigderson获图灵奖的核心贡献之一。

Q3: 零知识证明为什么重要？零知识证明让你在完全不泄露任何秘密的前提下，让对方相信你确实拥有某个秘密或完成了某个计算。Wigderson等人1986年证明的普遍性定理说：任何NP命题都有零知识交互式证明。这意味着密码协议中任何"我做了该做的事但不想让你看到细节"的需求，理论上都有解决方案。今天区块链和隐私计算中大量使用的ZK技术，根基在此。