图灵和阿贝尔双料专访：P与NP

近日，图灵奖与阿贝尔奖双料得主艾维?维格德森（Avi Wigderson）接受瑞安·彼得曼（Ryan Peterman，Ins前工程师、播客主）专访，就P与NP问题、零知识证明、量子计算展开讨论。几年前Avi Wigderson患淋巴瘤癌症并积极接受治疗，顺利康复后不久，分别斩获阿贝尔奖和图灵奖。

图源：Ryan Peterman @YouTube

第一章：引言

第二章：P 与 NP 问题

第三章：放宽正确性约束会怎样

第四章：NP 完全问题为何彼此等价

第五章：时间复杂度与空间复杂度

第六章：为何业界广泛使用可满足性求解器

第七章：随机性也是一种计算资源

第八章：随机性依赖于观测者的计算能力

第九章：零知识证明及其意义

第十章：量子计算带来的变革

第十一章：数学与计算机科学的关系

第十二章：科研生涯中的重大突破

第十三章：给年轻时的自己的建议

第十四章：结束语

第一章：引言

倘若未来有人找到了可在多项式时间内运行的经典整数分解算法，我认为整个世界都会陷入混乱。

本期嘉宾是艾维?维格德森（Avi Wigderson），图灵奖与阿贝尔奖双料得主。本次访谈，我和他深入探讨了他所研究的领域。

P 与 NP 问题，本质上关乎我们能否解开所有真正想要攻克的难题。随机性的优劣，取决于观测者本身，更取决于观测者的计算能力。如果有人宣称证明了 P 不等于 NP，要如何让我信服？可即便如此，我对他们的证明思路依旧一无所知。要知道，就连不可计算类的问题，他们也能找到对应的解决办法。试想，假如某天有人攻克了 NP 完全问题的高效解法，我们的世界又会变成什么样？

以下是本期完整访谈内容。

第二章：P与NP问题

问：您在一场讲座中提到，从哲学层面来讲，P 与 NP 问题触及了人类认知的终极边界。那么 P 与 NP 问题究竟是什么？它又和人类认知有着怎样的关联？

我用通俗易懂的方式，从宏观层面来讲。生活中存在各式各样的问题：数学难题、科学课题、医学难题、个人琐事、各类智力问题。计算机科学的核心，就是用计算机来解决问题。我们尝试对可求解的问题进行分类，以此厘清人类认知的边界。能被我们解开的问题，就是我们能够掌握、理解的内容，而人类想要探索的问题数不胜数。

首先来说 NP 类问题，人类所有想要解答的问题，基本都归属于 NP 范畴。在 NP 问题集合中，又划分出一个子集，也就是我们目前能够实际求解的问题。而我们真正关注的，是理论上所有可被求解的问题。

因此，P 与 NP 的核心命题就是：我们是否有能力解开所有渴望解答的难题，是否能够知晓一切想要探寻的真相。这一问题，直指人类认知的极限。

接下来我解释一下这些数学定义的类别为何对应这样直观的含义。先看 P 类问题：所谓可求解，指的是借助现有设备与高效算法，在有限时间内得出答案。手机里各类应用就是典型例子，比如导航软件，背后就有一套高效算法，能够在任意地图上计算出两点之间的最短路径，这类问题都属于 P 类。

而人类想要探究的问题，大多属于 NP 类。NP 类问题的定义是：我们暂时无法判断求解难度，但如果有人给出了一个答案，我们可以轻松验证这个答案是否正确。

为何人类探索的所有问题都具备这一特征？不妨换位思考：人若是下定决心钻研一个问题，最基本的前提就是，当你找到答案时，能够识别出这就是正解。倘若即便找到了答案也无从分辨，那人们根本不会着手去寻找。

数学家钻研定理证明，他人写出证明过程，我们就能核验真伪；科学家研究行星、细菌等各类数据，构建理论学说，理论必须与观测数据相符，我们也能判断这套理论是否成立；工程师承接项目，在资金、物理条件等各类约束下设计桥梁、电子设备等产品，委托方可以直观检查成品是否符合要求；侦探侦破案件，最终梳理出的案情逻辑也能被大众验证。

类似的例子还有很多。人类几乎所有重要的探索活动，都遵循同一个规律：答案一旦出现，便能被轻松识别。

总结来说：

NP 代表人类所有想要解答的问题，P 代表人类能够实际求解的问题。二者是否等价，就是 P 与 NP 问题的核心。

如果 P 等于 NP，那就意味着：只要一个答案能够被轻松验证，我们就一定能高效找到它。攻克癌症、破解各类难题，所有想象得到的目标都有实现的可能，人类将能够洞悉一切想了解的事物。这无疑是关乎人类认知本质的终极问题。

问：这也是七大千禧年大奖难题之一，破解该问题就能获得百万美元奖金。这个问题存在两种可能性：证明 P 与 NP 等价，或是证明二者不等价。如果让你凭直觉预测，未来究竟会得出哪一种结论？原因是什么？

包括我在内，几乎所有理论计算机领域的学者都倾向于认为P 不等于 NP，不过支撑这个观点的理由，其实并不算绝对严谨。

第一点，来自生活直觉：寻找答案的过程，远比验证答案要困难。举个例子，你弄丢了钥匙或手机，四处寻觅毫无头绪，但如果有人告诉你东西放在窗台，你一眼就能确认。现实经验告诉我们，“寻找” 往往难于 “核验”。

第二点，NP 类问题在各个领域无处不在：优化问题、逻辑问题、数学问题，还有算法、协议、安全系统的可靠性验证等等，其中大量都属于 NP 问题甚至 NP 难问题。过去六七十年间，无数研究者针对不同场景下的这类问题，尝试寻找高效算法，最终全都无功而返。这似乎暗示着，通用的高效解法并不存在。

从技术层面来讲，NP 问题（尤其是 NPC——NP完全问题），往往需要在指数级规模的解空间中逐一检索。P 与 NP 之争，本质就是能否找到一种巧妙的通用方法，把指数级的检索范围压缩到合理区间 —— 如果能做到，就证明 P 等于 NP。但目前学界普遍认为，这样的方法并不存在。

当然这些都只是基于经验的推测。倘若某天有人凭借全新思路，找到了 NP 完全问题的高效算法，整个世界都会被彻底改变。

问：在软件工程领域，我们一直在使用各类算法。很多难题原本只能依靠暴力枚举，复杂度极高，而优秀的算法能将其转化为多项式时间可解的问题。但面对 NP 问题，目前最优的解法依旧逃不开暴力枚举，我这样理解是否正确？

你的理解完全准确。具体来说，一个 NP 完全问题会包含无数个具体实例，比如旅行商问题，对应着各式各样的地图与路网。我们评判一套算法是否高效，标准是它能否对所有实例都做到高效且正确求解。

但软件工程、现实优化场景中，人们遇到的往往只是一小部分特殊实例。举个例子，协议验证、生物学中的蛋白质折叠问题，都属于 NP 难问题。蛋白质折叠需要在分子、原子的化学规则约束下，实现系统能量最小化，这是典型的优化难题。可人体却能无时无刻、高效地完成蛋白质折叠，这是什么原因？

其实目前我们也没有标准答案。一种推测是，生物演化让自然界的蛋白质具备了特殊结构，人体接触到的蛋白质种类有限，并非指数级数量，这类蛋白质本身就更容易实现能量最小化。

放到软件工程、程序验证与测试领域也是同理。我们通常会把需求校验问题，转化为布尔公式的可满足性问题。这类实际场景生成的问题实例，本身带有特殊结构，贪心策略或是其他精巧算法就能奏效。简单来说，现实中遇到的实例，大多不是复杂度最高的最坏情况。

这样的案例有很多，也有严谨的理论证明。比如求解线性规划的单纯形法，从理论上讲，它面对最坏情况的不等式组时，复杂度是指数级的，但在实际应用中，运行效率接近线性。这是因为现实里的线性方程组都带有额外结构，让这套算法得以高效运行。如今学界虽然找到了能适配所有线性规划问题的高效算法，但逻辑复杂，实际应用并不广泛，单纯形法反而因简洁实用被沿用至今。

第三章：放宽正确性约束会怎样

问：你刚才提到了蛋白质折叠问题，这类 NP 问题并没有追求百分之百精准求解，而是给出结果并附上置信度，允许一定误差。那么对于 P、NP 类问题，如果我们放宽绝对正确的要求，算法的渐进复杂度是否能摆脱指数级？

这是一个很有价值的思考。你提到的蛋白质折叠相关算法应该是AlphaFold阿尔法折叠，它依托现有蛋白质数据训练而成，即便面对从未见过的蛋白质样本，表现也十分出色。究其原因，还是因为现实中的蛋白质实例自带特殊结构，能够被高效求解。

当 NP 完全（即NPC）或 NP 难问题无法做到精准求解时，放宽要求、采用近似算法，是业界最常用的思路。我先明确概念：NP 完全问题是 NP 类中难度最高的问题，只要找到其中一个问题的高效解法，就能破解所有 NP 问题；反之，只要证明其中一个问题难解，就能证明全体 NP 问题难解。旅行商问题、能量最小化框架下的蛋白质折叠问题，都属于 NP 完全问题。

既然这类问题不存在通用的精准高效算法，人们便转而追求近似解：不要求结果达到理论最优，允许和最优值存在一定偏差，比如偏差比例控制在二分之一、百分之十以内。

NP 完全理论诞生于上世纪 70 年代初，而 90 年代出现的PCP 定理是一项重大突破。这一定理证明：即便是求解近似解，很多 NP 问题依旧难度极高。

举个例子，布尔公式可满足性问题：我们希望找到一组变量赋值，满足全部约束条件。如果放弃百分之百满足，改为满足百分之九十的约束，难度是否会降低？答案是否定的。

以每个约束仅包含三个变量的情况为例：哪怕完全随机赋值，也能满足约八分之七的约束条件。而 PCP 定理，再结合赫斯塔德（Johan H?stad）的强化结论可以证明：只要你想在随机猜测的基础上，再多满足哪怕极其微小的一部分约束，这个问题就会变回 NP 难问题。

也就是说，对于大量约束优化类 NP 问题，别说找到最优解，哪怕只是想得到一个 “比随机猜测好一点点” 的近似解，难度都和求解最优解完全一致。

问：你介绍了 NP、NP 完全、NP 难这些复杂度类别，我了解到复杂度领域还有更多分类，能否整体介绍一下复杂度体系？

确实，计算复杂度领域有着庞大的分类体系，学界甚至专门搭建了 “复杂度动物园” 网站（ complexityzoo.net ），收录了数百种复杂度类别，该网站由斯科特?阿伦森（Scott Aaronson）创立。

划分复杂度类别的核心依据，是算法求解问题所消耗的资源量。

P 类（多项式时间）：问题的求解时间，与输入数据规模呈多项式关系。线性时间、二次时间、三次时间都属于多项式时间，理论上都被视作高效算法。

NP 类：不关注求解耗时，而是要求验证答案的时间为多项式时间。

除了多项式时间、指数时间，还有双重指数时间等更多时间复杂度划分。

图灵的经典理论早已证明：存在一部分问题，计算机根本无法求解，这类问题被称为不可判定问题，这也是复杂度研究的起点。

时间只是其中一种资源。从理论和实际应用出发，我们还会考量其他资源：

存储空间：如何最小化计算过程占用的内存；

通信开销：多方协作计算时，数据交互的传输量（比如卫星通信，需要尽量减少通信次数与数据量）；

能耗、并行计算能力：使用多台计算机并行运算时，问题的提速上限。

复杂度理论的一大核心方向，就是根据资源消耗对问题分类，并研究不同复杂度类别、不同问题之间的关联。

举个例子：我们尚且无法判定所有 NP 完全问题的难易，但已经找到了它们之间高效的归约方法。假设你掌握了解数独的高效算法，就能通过归约，将布尔可满足性问题、旅行商问题、整数分解问题等，全部转化为数独问题求解，反之亦然。

因此，即便我们不清楚单个问题的复杂度，也能通过问题间的归约关系，梳理出不同问题的难度层级。这些问题一部分源于现实技术约束，另一部分则来自纯粹的数学探索。

第四章：NP 完全问题为何彼此等价

问：你提到所有 NP 完全问题都是等价的，如何将布尔可满足性问题等价转化为图着色问题？这类转化是通用逻辑，还是针对特定问题定制的？

这是一个很好的问题。不同 NP 完全问题之间的转化，我们称之为归约算法。绝大多数归约逻辑都比较简单（PCP 定理相关的归约除外，它的逻辑极为复杂），而且归约是双向成立的 —— 因为双方都是 NP 完全问题。

最早被证明为 NP 完全的问题，就是布尔可满足性问题，史蒂芬·库克（Stephen Cook）和列昂尼德·莱文（Leonid Levin）在奠基性论文中，首次定义了 NP 完全（即NPC，NP-Complete），并以它为范本展开证明。而所有其他 NP 问题，都可以归约为布尔可满足性问题，核心原因在于：计算本身具有局部性。

无论是笔记本还是其他计算设备，本质都是对二进制位做局部运算：读取两个寄存器的数据、做加法、异或、与运算等，通过一连串简单的局部操作，最终得出结果。

计算过程中，设备的存储状态会逐步变化，而每一次状态改变都只涉及局部数据。我们可以把整个计算流程，转化为一系列约束条件，进而构建出布尔可满足性问题。这也是绝大多数 NP 完全问题能够互相归约的根源。

我举一个最简单的例子：整数分解问题如何归约为布尔可满足性问题。如果有人给出了一个整数的因数，我们只需做乘法运算，就能验证答案是否正确。乘法本身就是一套基础的局部运算，我们可以把完整的乘法计算流程，拆解成一条条布尔约束。只要有人猜出因数（这正是 NP 问题 “给出答案即可验证” 的特性），就能通过约束完成核验。

同理，图着色、数独等问题，都可以依托 “局部约束” 这一特性，完成和布尔可满足性问题的互相归约。

第五章：时间复杂度与空间复杂度

问：刚才聊了时间复杂度和空间复杂度。在软件工程中，我们常常需要在二者之间做取舍，目前有没有成熟的理论，来解释时空复杂度的权衡规律？

时空资源的权衡，是复杂度领域的经典研究方向，不同问题的表现也各不相同。部分问题存在明确的约束：比如某类运算的时间复杂度与空间复杂度的乘积，至少是输入长度的平方。这类问题有两种解法：一是使用极小的空间（对数空间），但要付出平方级的时间；二是采用线性时间运行，同时占用接近线性的空间。

不同计算模型下，这类时空权衡的结论也会存在差异。但有几个普适性的经典结论：

基础辨则：如果一个算法的运行时间为 t，那么它占用的存储空间绝不会超过 t，因为计算机运行时不会访问超出时长的存储单元。

五十年前，瓦连特（Leslie Valiant）、保罗（Wolfgang Paul）和霍普克罗夫特（John Hopcroft）做出改进：运行时间为 t 的计算，可以转化为存储空间约为 t/log t 的等价计算。这套方案会大幅增加运行时间，但能节省空间。在很长一段时间里，学界都认为这就是时空优化的极限，并且在部分简化计算模型中，也证明了无法再进一步优化。

而去年，瑞安?威廉姆斯（Ryan Williams）取得了重大突破：任意运行时间为 t 的计算，都可以改写为仅占用√t 存储空间的算法，空间压缩幅度远超以往。这套算法逻辑十分精巧，核心技术依托于史蒂夫?库克（Stephen Cook，NP 完全理论奠基人之一）之子詹姆斯?库克（James Cook），以及伊恩·默茨（Ian Mertz）此前的研究成果。当然，它的代价依旧是运行时间大幅增加，但也证明了时空复杂度之间，存在远比想象复杂的关联。

问：这套结论是针对图灵机模型吗？普通随机访问计算机是否适用？

这套理论很难用通俗语言拆解技术细节，我举一个更早的经典案例，帮你理解 “极小空间完成复杂计算” 的神奇之处。

四十多年前，戴夫?巴林顿（David A. Mix Barrington）发现了一个有趣现象：多数判定问题（给定一串二进制数，判断 0 多还是 1 多），常规思路需要对数空间来统计数量，这看起来是空间的下限。但他设计出一套算法，仅用常数空间就能解决这个问题。

前提是可以随机读取序列中任意位置的二进制位。这套算法的核心是非交换代数。简单解释：先后执行两个操作，调换顺序后结果会完全不同，这就是非交换性。比如先翻转图形、再旋转，和先旋转、再翻转，最终形态不一样。

巴林顿用五阶置换（正五边形的旋转、翻转操作）来编码二进制位：读到 1 就执行旋转，读到 0 就执行翻转。整个过程只需要记录正五边形的形态，全程仅占用常数空间。而操作的非交换性，可以模拟出与门、或门等基础逻辑运算。

这里有一个经典趣味谜题，可以直观理解这个原理：有一幅画，两端系着绳子，墙面有两颗钉子。要求把画挂在两颗钉子上，拔掉任意一颗钉子，画都会掉落。如何缠绕绳子？这个谜题的解法，正是利用了操作的非交换性，和上述算法的底层逻辑相通。

双钉挂画谜题解法（拔任意一钉画必掉）

图源：顾森《浴白里的惊叹》人民邮电出版社

§1 几何问题 第27题 插图（作者妻子雪琴制作）

这个案例也能说明：很多看似需要大量空间的计算，都能借助特殊数学方法，在极小空间内完成。巴林顿的这项成果实用性极强，如今在密码学领域有大量应用。而且这套算法的时间复杂度仅为平方级，效率很高。

问：你刚才提到，这套算法不需要记录最终统计数值，只需要输出 “0 更多” 或 “1 更多” 这类判断结果。也就是说，只要是二值判定问题，无论输入规模多大，都能依靠常数空间求解，对吗？

没错。如果问题要求输出完整的统计数字，就必须占用对应空间；但仅需给出 “是 / 否” 的判定结果，就可以借助这类方法突破常规空间限制。

第六章：为何业界广泛使用可满足性求解器

问：我们聊过 NP 完全问题彼此等价，我发现现实中很多工程师解决各类难题时，都会直接使用布尔可满足性求解器。但问题转化的过程会增大实例规模，按理说效率会降低，大家为何依旧选择这种方式？

核心原因很简单：多年来，学术界和产业界针对布尔可满足性问题，研发了海量精巧的启发式算法，专门适配现实场景中带有特殊结构的实例。

这类启发式算法不会盲目枚举所有可能性，而是优先锁定关键变量：部分变量一旦确定取值，会连带约束大量其他变量，以此大幅压缩检索空间。

当然，在理论最坏情况下，这类优化毫无作用。学界也有相关猜想：布尔可满足性问题的最坏复杂度，就是 2 的常数倍 n 次方，不存在指数级以下的通用解法。

但现实场景里，各类工程问题转化而来的布尔公式，大多带有天然结构，启发式算法可以高效求解。除此之外，使用可满足性求解器也十分便捷：程序、通信协议的合规性校验，很容易转化为布尔约束问题，这也是它在工程领域普及的重要原因。

第七章：随机性也是一种计算资源

问：我们聊了算法用到的各类资源。你在讲座中提出，随机性也是算法的一种资源，这句话该如何理解？

随机算法的应用由来已久，抛硬币、统计抽样都是利用随机性。计算机普及后，人们发现引入随机选择，能极大提升各类计算的效率。

举个经典例子：大数素性检测。过去人们一直找不到高效的确定性算法，直到上世纪 70 年代，米勒（Miller）、拉宾（Rabin）等人提出了随机素性检测算法，完美解决了这个难题。

随机算法的定义：算法运行过程中，可以做出随机选择。我们可以形象理解为设备内置了一枚公平硬币，每次选择都由抛硬币决定。

但现实中，计算机并没有真正的 “抛硬币” 装置，高质量的随机数本身需要消耗资源（时间、硬件、算力）。目前获取随机数的常见方式分为几类：

采集物理噪声：计算机热噪声、网络流量、硬件传感器数据等，这类随机源成本低，但随机性无法保证绝对均匀独立；

伪随机数生成器：线性同余发生器、截取圆周率数位等，本质是确定性运算，只是结果看起来近似随机；

量子随机源：利用光子自旋等量子现象，理论上能生成绝对均匀、相互独立的随机位，但硬件成本极高，且无法做到完美无瑕疵。

随机算法普遍存在微小的出错概率，这是和确定性算法最大的区别。因此，把随机性视作一种计算资源，是复杂度理论里的标准视角：我们需要研究使用多少随机位、随机位的质量高低，才能在出错率可控的前提下完成计算。

由此也衍生出一大研究方向：去随机化，也就是尽量减少算法对真随机数的依赖。理想状态下，用少量真随机位，通过确定性运算生成海量伪随机序列，并且这些伪随机序列，在对应算法中表现和真随机序列毫无区别。

素性检测算法的发展就是典型案例。高斯数百年前就提出了大数素性检测的难题，长期以来，大家都依赖随机算法，且无法减少随机位的使用。直到 21 世纪初，阿格拉瓦尔（Agrawal）、卡亚尔（Kayal）和萨克塞纳（Saxena），结合数论知识，分析了原有随机算法对随机性的使用逻辑，最终推导出AKS确定性素性检测算法。

判断随机位质量的标准，本质就是伪随机性的定义：一套伪随机序列是否合格，不看它本身是否 “真随机”，只看目标算法能否区分它和真随机序列。

部分算法并不要求所有随机位相互独立，仅需要两两独立、三三独立即可。这类算法对随机性的要求更低，只需极少量真随机位，就能生成满足条件的伪随机序列。

我很认同一句话：随机性的优劣，取决于观测者，取决于观测者的计算能力。我们不必纠结序列本身是否绝对随机，只要运行算法的观测者无法分辨真伪，这套伪随机序列就完全可用。

第八章：随机性依赖于观测者的计算能力

问：你多次提到，随机性由观测者的计算能力决定，能否用通俗的例子解释这一点？

这个例子来自曼纽尔?布鲁姆（Manuel Blum）和西尔维奥?米卡利（Silvio Micali）的经典论文。

我们模拟一组实验：我抛一枚硬币，你来预测落地结果。

无辅助工具：硬币抛出后两秒落地，你仅凭肉眼预判，猜对概率只有二分之一。对你而言，抛硬币是完全随机的，信息熵达到最大值；

配备普通电脑：依旧来不及计算硬币的运动轨迹，结果和第一种情况一致；

连接超级计算机 + 高清传感器、摄像头：设备可以瞬间计算出硬币的角动量、下落距离、空气湿度等所有参数，精准预判落地正反面。此时对你而言，抛硬币不再有随机性，信息熵为零。

整个实验中，抛硬币这个物理事件本身没有任何变化，唯一改变的，是观测者的计算能力。

传统数学、物理、哲学领域定义随机性，都聚焦于事件本身；但复杂度理论视角完全不同：我们不关注事件，只关注观测者与计算模型。一个事件是否随机，完全取决于观测者能否凭借自身算力预判结果。

这套理论是去随机化研究的核心基础。如果我们假设P 不等于 NP（或是存在其他高复杂度的难解问题），就能推导出一个重要结论：P 类问题等价于 BPP 类问题。(BBP，即Bounded-error Probabilistic Polynomial Time)

简单解释：所有存在高效随机算法的问题，都一定存在对应的高效确定性算法。想要实现去随机化，前提是存在算力无法破解的 “难解函数”。

这也引出了复杂度领域的核心范式：问题难度与随机性相辅相成。二者的关联是双向的：一方面，问题存在计算难度，我们就能借此构造伪随机序列、实现去随机化；另一方面，如果我们成功实现了某类算法的去随机化，也等价于证明了对应问题具备计算难度。

正因学界普遍相信 NP 问题难以求解，大家也倾向于认为：算法中使用的随机性，大多可以被消除。

问：能否直观解释问题难度和随机性的关联？

可以。假设你是一台算力有限的计算机（仅能运行多项式时间算法），面对旅行商这类难题，你无法直接得出答案，答案对你而言就存在不确定性，这就是信息熵。

我们需要借助技术手段放大这种不确定性：让随机生成的问题实例，对于多项式时间算力的观测者而言，答案对错的概率无限接近二分之一，观测者哪怕比随机猜测多赢一点点都做不到。这就是利用问题难度制造高质量随机源。

基于这个思路，学界研发出了随机放大技术。而伪随机数生成器的逻辑恰好相反：用少量真随机位（种子），生成海量伪随机位，并且即便观测者算力有限，也无法发现这些伪随机位之间的关联。

我和尼桑（Nisan）共同提出的 NW 伪随机生成器，就是这类技术的代表。打个比方：攻克一个难解问题，就好比赚到第一笔一百万；有了第一个一百万，就能衍生出更多财富。同理，依托一个难解函数（第一份 “随机性”），就能生成海量彼此无关联的伪随机序列。

问：回到你之前的观点：如果拥有无限算力，世间就不存在真正的随机事件，比如天气、抛硬币都能被精准预测。这个说法准确吗？

从算法、计算的角度来看，这句话是成立的。拥有无限算力，就能轻松区分真随机序列和低熵伪随机序列。

但也要区分场景：如果我们的目标不是运行算法，而是纯粹生成随机事件（比如密码、密钥），规则就变了。香农信息论明确指出：密码的安全性，完全取决于随机源的信息熵。

这种场景下，我们要求事件本身的概率严格为二分之一，和观测者的算力毫无关系。哪怕对方拥有无限算力，也无法改变事件本身的随机属性。这是信息论层面的硬性要求，和计算复杂度是两个维度。

问：我还了解到，可以整合多个低质量随机源，生成高质量随机数，这是什么原理？

这属于随机提取 / 随机提纯理论，和伪随机理论关联紧密，但研究方向不同。

现实中我们很难获取完美的真随机源，天气、量子现象、太阳黑子、股价走势等，都属于弱随机源：它们存在一定不可预测性，但带有偏差、关联性，信息熵不足。

随机提纯的目标，就是对这类含部分信息熵的弱随机序列做处理，提取出质量更高的随机位。理论证明：无法用单个弱随机源，提取出少量完美随机序列，但可以生成多项式数量的输出块，其中99%以上都是完美随机序列，仅有极少数存在缺陷。

使用时只需对所有输出块运行算法，再取结果的多数票，就能规避缺陷块带来的影响。这套理论体系已经发展得十分成熟，也衍生出多种不同前提条件下的实现方案。

问：你提到的二维数组、矩形图示，大概率和和积定理有关，这是多弱随机源提纯的核心工具。

简单讲解和积定理：我们取一组整数，计算所有两数之和，再计算所有两数之积。如果一组数字求和后数量增长有限，那么求积后数量一定会大幅增加；反之，如果求积后增长有限，求和后必然大幅扩张。和与积两种运算，具备 “互补” 特性。

在随机提纯中，我们将多个弱随机源的输出视作数字，混合使用加法与乘法运算。依托和积定理，就能保证输出结果的多样性大幅提升，也就是信息熵增加。这套方法可以逐步叠加，最终从多个弱随机源中，提取出接近满熵的高质量随机序列。

需要说明的是，和积定理仅适用于多个相互独立的弱随机源，单个弱随机源的提纯，还需要依靠其他技术。

第九章：零知识证明及其意义

问：了解到你在零知识证明领域有深入研究，能否解释什么是零知识证明，以及它的价值？

零知识证明（ZKP）如今已经走出理论圈，被大众熟知。它的概念最早出自戈德瓦瑟（Shafi Goldwasser）、米卡利（Silvio Micali）和拉科夫（Charles Rackoff）的经典论文，这篇论文同时还定义了交互式证明。

传统数学证明是书面形式，而交互式证明允许双方实时对话，并且验证方可以引入随机选择。证明者向验证方论证一个命题，整个过程存在极小的误判概率，而这个概率可以被无限压低。

零知识证明，是交互式证明的特殊形式：证明者可以让验证方确信命题为真，但验证方不会从交互过程中，获得除 “命题为真” 之外的任何额外信息。

这个概念初听十分反直觉：如何在不透露任何解题思路、答案细节的前提下，说服别人你掌握了正确解法？举个例子：如果有人宣称证明了 P 不等于 NP，并用零知识证明说服我，我最终只会确信这个结论成立，但完全无法知晓他的证明过程。

零知识证明的核心应用场景是密码学。在各类密码协议中，用户需要使用私密信息完成运算，协议需要确保用户没有作弊，但又不能泄露隐私。

典型案例：公钥密码体系中，公钥由两个大质数相乘得到。我需要向对方证明：我给出的数字确实是两个质数的乘积，但绝对不能泄露这两个质数本身。零知识证明就能完美实现这一点。

后续我与奥德·戈尔德赖希（Oded Goldreich）、西尔维奥?米卡利（Silvio Micali）合作证明了一个重磅结论：零知识证明具备普适性。任何拥有传统数学证明的命题，都可以构建对应的零知识交互式证明。无论是数学定理、密码学命题，都能在保密核心信息的前提下完成论证。

问：它的底层原理是什么？比如把 P 对 NP 的证明转化为零知识证明，具体如何实现？

首先需要一个基础前提：单向函数存在。单向函数指正向计算简单、逆向求解极难的函数，整数分解、离散对数都是公认的单向函数，整个密码学体系都建立在这个假设之上。

依托单向函数，可以构建承诺方案：我拥有一个私密数字，对外公布一串看似随机的公开数据。这串公开数据有两个特性：第一，旁人无法反推出我的私密数字；第二，我事后也无法篡改最初的私密数字，相当于 “立下承诺”。两个质数的乘积，就是最简单的承诺方案实例。

我用三染色问题（经典 NP 完全问题）举例，讲解零知识证明的完整流程：命题：我们双方都知晓一张图，我宣称可以用三种颜色给所有顶点染色，保证相邻顶点颜色不同。我要在不透露具体染色方案的前提下，证明这个命题。

流程循环执行以下步骤：

我为每个顶点的颜色生成一份承诺，对外公布，不直接展示颜色；

你随机挑选图中的一条边，要求我公开这条边两个顶点的承诺（解密）；

你核验：两个颜色都属于指定三色，且二者不相同。

正确性（防止证明者作弊）：

如果这张图本身无法完成三染色，就必然存在相邻顶点同色、或是使用违规颜色的漏洞。

你随机挑选边，就有概率抓到漏洞。反复执行上万次后，我作弊却不被发现的概率会指数级趋近于零。

零知识特性（不泄露答案）

如果我每次都使用同一套染色方案，多次核验后你就能拼凑出完整方案。因此我每次都会随机置换三种颜色的命名（红、绿、蓝重新分配）。

一张合法的染色方案，通过颜色置换能衍生出 6 种等价的合法方案。每次核验相邻两个顶点时，你看到的都只是两个随机且不同的颜色，无法从中总结出任何有效信息。一轮交互结束，你一无所获，自然也就无法还原完整染色方案。

依靠这套逻辑，我们就能为三染色问题构建零知识证明。

再结合 NP 完全问题的归约特性：所有 NP 问题都可以转化为三染色问题，并且原问题的 “证明 / 答案”，也会同步转化为图的合法染色方案。因此，只要三染色问题可以实现零知识证明，所有 NP 问题都能实现零知识证明。

补充一点：零知识证明并非绝对零误差。如果命题本身为假，证明者侥幸蒙混过关的概率可以压缩到无限小，但无法彻底降为零；如果命题为真，那么验证结果绝对无误。

第十章：量子计算带来的变革

问：我们聊到了密码学的单向函数，而量子计算的出现，极大改变了复杂度理论。你如何看待量子计算对整个领域的影响？

量子力学是描述客观世界的基础理论，学界自然会思考：能否让计算机遵循量子力学规则运行？

量子计算机依托量子叠加态和幺正变换工作，和经典计算机、随机计算机有本质区别。量子世界存在干涉效应，可以理解为 “概率能够相互抵消”，运算逻辑远超传统概率范畴。

从计算模型层级来看：量子计算机的能力，至少强于所有经典随机计算机。因为对量子比特做测量，本身就能得到真随机位。

量子计算的概念在上世纪 80 年代由费曼等人提出，最初目的是模拟复杂的量子物理系统。很长一段时间里，量子算法只存在于理论模型中，无法解决现实中的经典难题。

1994 年，彼得?肖尔（Peter Williston Shor）取得颠覆性突破：他设计出量子算法，可以在多项式时间内完成整数分解和离散对数求解。而这两个问题，正是现有公钥密码体系的安全根基。这个结果震惊了整个学界和产业界。

自此之后，各国政府、企业投入巨额资金研发量子计算机。但量子计算的落地面临巨大技术难题：

量子叠加态极其脆弱，外界环境的微小吧扰都会破坏计算状态，远不如经典硬件稳定；

量子纠错码可以缓解噪声问题，但也只是解决方案之一，硬件层面依旧存在大量待攻克的技术壁垒。

量子计算的崛起，也倒逼密码学完成全面革新：

如果未来有人研发出经典多项式时间整数分解算法，现有金融、互联网的安全体系都会彻底崩溃。而肖尔算法证明，成熟的量子计算机可以直接破解现有主流公钥密码。

因此，当下密码学的核心目标，是寻找连量子计算机也难以求解的数学难题，搭建抗量子攻击的新密码体系。

单向函数在自然界中十分普遍（比如鸡蛋做成煎蛋无法逆向复原），但能构建公钥体系的陷门单向函数十分稀少。继整数分解、离散对数之后，格密码、带误差学习问题，成为抗量子密码的主流候选方案。截至目前，学界依旧没有找到破解这类问题的高效量子算法。

量子计算还让计算机科学、物理学深度融合：算法思想开始应用于量子引力、黑洞等前沿物理研究；同时物理领域的新发现，也反哺计算模型与复杂度类别。

还有一项极具颠覆性的理论成果：多年前学界证明了MIP*=RE。

简单解释：引入量子证明者、量子纠缠的交互式证明系统，可以让经典意义上不可计算、不可判定的问题，被高效验证。

这个结论看似脱离现实，却衍生出全新的数学工具，成功解决了数学、物理领域多个悬而未决的经典猜想。这套理论诞生于复杂度学者构建的抽象模型，最终却成为攻克硬核难题的利器，这也是计算理论最迷人的地方之一。

这类长达两百页的复杂论文，结论又十分颠覆，学界要如何核验其正确性？

这是所有高深数学成果都会遇到的问题。P 与 NP、黎曼猜想时常出现各种 “证明版本”，很多都需要漫长时间核验、推翻。克莱数学研究所的千禧年难题之一 —— 庞加莱猜想，其证明也耗费了数年时间梳理细节、修正漏洞。

MIP*=RE 的原始论文确实存在小漏洞，不过很快就被修复。在数学领域，理论的真伪本身就是学术界集体论证、达成共识的过程。如今形式化证明工具（比如 Lean）逐步成熟，未来复杂证明的核验，也会变得更加规范。

第十一章：数学与计算机科学的关系

问：你的研究兼具计算机科学与数学属性，在你看来，二者之间是什么关系？

我所研究的复杂度理论、算法理论，是站在数学与计算机科学交叉地带的学科。一方面，我们的产出是标准的数学定理与严格证明，和代数、分析、拓扑等纯数学分支别无二致；另一方面，我们的研究问题、模型，全都围绕计算展开。

计算无处不在：代码运行、蛋白质合成、生物繁衍、天气演变，本质都是一系列基础局部操作的连续演化。我们研究计算，核心是分析计算过程消耗的各类资源，理解自然现象背后的运算逻辑。

这个交叉领域能同时吸收两方面的养分：工业界、硬件系统为我们提供现实问题；纯数学为我们提供严谨的推理工具。我们构建模型、定义概念，有时是为了解决实际问题，有时纯粹是出于理论探索的审美与兴趣。

很多人认为理论计算机科学是 “为了做题而做题”，但我做研究从来不以应用为首要目标。支撑我数十年深耕这个领域的动力是什么？

首先要厘清一点：我们做的核心工作，是构建模型，而非单纯解题。提出新定义、搭建新模型，是这个领域的核心，这一点甚至比传统数学更加突出。比如我们重新定义的 “随机性”，就衍生出大量颠覆性结论。

我本科、研究生、博士后阶段都深耕计算机科学，这让我对 “计算” 本身抱有天然的兴趣。随着领域发展，计算理论已经渗透到物理、生物等所有学科，成为理解世界的基础视角，这本身就极具吸引力。

从业四十五年，我见证了理论成果不断落地：零知识证明最初被我认为落地成本极高，几乎不会被实际应用，但如今它在区块链、隐私计算等领域大放异彩；PCP 定理重塑了编码理论；密码学、量子算法更是深刻改变了整个科技行业。

当然，领域内也存在大量短期内看不到落地价值的问题，P 与 NP 就是典型。我们至今都无法证明基础结论，甚至连 “乘法比加法更难” 这种简单猜想都无法证实。但研究这些问题，是为了探索计算能力的边界：什么能算、什么不能算，资源该如何取舍，不同问题之间存在怎样的关联。

目前人类对于 “计算” 的理解，依旧处于初级阶段。哪怕研究成果暂时无法落地，探索本身也具备独一无二的价值。

这个领域的科研日常和工程岗位截然不同：工程师每年都能产出落地项目，但理论研究者绝大多数时间都在不断试错、思考，一整天毫无进展是常态。但试错的过程并非毫无意义，很多灵感都会在反复失败中慢慢积累。只有真正享受思考、享受探索的人，才能坚持下来。

第十二章：科研生涯中的重大突破

问：理论领域的重大突破往往间隔数十年。当你取得里程碑式的研究成果时，内心是怎样的感受？

取得重大发现的时刻，自然会感到欣喜，但这类机遇十分稀少。

整个科学领域的进步，更像蚂蚁搬家：成千上万的研究者，每年产出海量论文，绝大多数成果都是微小的改进 —— 优化一个边界、改良一种技巧、补充一个案例。这些细碎的进展看似不起眼，却是整个领域向前推进的基石。

真正颠覆性的成果可遇不可求。就像巴林顿发明常数空间计数算法时，他最初的目标其实是证明 “这件事不可能完成”，最终却意外得到了相反的结论。这种突破固有认知的发现，会给研究者带来极大的震撼。

我常对学生和博士后说：不要为了百万美元奖金去研究千禧年难题。投身这个领域，核心是享受思考的过程。

日复一日的试错确实枯燥，但每一次微小的收获，都会带来满足感。这也是理论研究独有的魅力。

第十三章：给年轻时的自己的建议

问：最后一个问题。以你多年的经验，如果回到职业生涯起点，你会对当初刚入行的自己提什么建议？

我很幸运，一路走来没有想要改变的选择。这个领域对年轻人十分友好，没有森严的等级，学术会议上，新人也能和顶尖学者平等交流。我求学时遇到了优秀的导师，职业生涯中也结识了无数出色的合作伙伴。

如果一定要给出一条通用建议，那就是：在职业生涯早期，去研究自己真正热爱的问题。

初入科研领域时，要多尝试不同方向，阅读不同领域的论文，接触不同类型的问题，摸索自己的天赋与兴趣所在。多数情况下，你最热爱的方向，也正是你最擅长的领域。

第十四章：结束语

非常感谢你抽出时间接受本次访谈。

感谢各位观看本期播客。如果喜欢本期内容，欢迎点赞、留言支持。大家有想要邀请的嘉宾，也可以在评论区推荐，往期多位嘉宾都是来自观众的提议。

除了播客之外，我目前在研发一款人体工学分体键盘，原型机已经完成，并在众筹平台上线，上线八小时就达成了众筹目标。感谢所有第一批支持的朋友。目前团队正在推进模具生产，众筹通道依旧开放，链接我会放在简介中。

再次感谢大家的观看，我们下期再见。