来源：市场资讯
（来源：图灵人工智能）
您想知道的人工智能干货，第一时间送达
P vs NP问题，理论计算机科学中的世纪未解难题，千禧年七大难题之一。听起来离普通人很远，但它关乎一个本质问题——如果所有难题都能被快速求解，世界会变成什么样？
2026年6月1日，瑞安·彼得曼对阿维·维格德森进行了一场深度访谈。这位普林斯顿高等研究院的赫伯特·马斯教授，是全球唯一同时拿下图灵奖和阿贝尔奖的学者——计算机科学和数学领域的双料最高荣誉。
他的研究覆盖计算复杂性理论、随机性、现代密码学、图论、量子计算。下面我们从P vs NP讲起，一路走到后量子密码学。
01 什么是P vs NP？
要理解P vs NP，先搞懂两个概念。
NP类问题：如果有人已经给出了答案，我们能在合理时间内验证这个答案是否正确。仔细想想，几乎所有人类想要主动解决的问题都属于NP——数学证明、科学理论、工程设计。我们找到答案时必须有能力识别出这就是正确答案。从这个角度看，NP代表了人类所有具备探索价值的问题集合。
P类问题：存在一套成熟算法，不需要任何人提供答案或提示，算法自身就能够在合理时间内直接算出正确结果。比如手机导航输入起点终点，软件自主计算最短路径——最短路径问题就是典型的P类问题。
P vs NP的核心追问：这两个集合是否相等？
如果P等于NP——所有能快速验证答案的问题，都能被算法快速求解。人类的科技发展将迎来指数级飞跃：复杂数学猜想的证明、疑难病症的治愈方案，都可以通过算法快速找到解法。
如果P不等于NP——世界上必然存在大量问题，答案可以被快速核验，却永远无法通过算法快速求解。这是目前绝大多数理论计算机科学家倾向的结论。
阿维·维格德森特别强调：目前所有的判断都只是学界的直觉，并没有严谨的数学证明。如果未来有人提出全新的研究思路，找到了NP完全问题的多项式时间算法，当下所有主流认知都会被推翻。
02 NP完全：攻破一个，就能攻破全部
所有NP问题背后遵循同一套底层逻辑。旅行商问题、数独、地图着色、布尔可满足性问题——应用场景不同，但验证过程本质都是计算机可以执行的局部操作。
任何一个NP问题的验证流程，都可以被完整翻译成布尔可满足性问题。基于这个结论，学界延伸出了NP完全问题这个关键概念：攻破一个，就能攻破全部。
经过几十年研究，全球已发现数千个NP完全问题，分布在数学、物理、生物、工程、经济学几乎所有主流领域。过去五六十年里，成千上万的顶尖研究者都在尝试寻找NP完全问题的高效解法——至今没有任何人成功。这也是绝大多数科学家相信P不等于NP最有力的现实依据。
但是，理论上的无解不等于现实中的无解。NP完全问题定义的“难度”针对的是最坏的输入场景——存在一部分极端案例，任何算法都无法快速求解。但现实中遇到的输入几乎都不会是这类极端案例。
数独就是例子。任意规格的数独都是NP完全问题，理论上存在大量极难求解的极端布局。但我们平时玩的9×9数独，出题者都刻意挑选了难度适中、有明确解法的布局。
既然精确解难以求解，能不能找近似解？PCP定理给出了让人意外的答案：对于某些问题，随机猜测就能满足87.5%的约束条件，而想把满足比例从87.5%提升到87.6%——难度和求解精确解完全等价。随机猜测达到的水平就是天然天花板，想再往前迈一小步都会撞上无法逾越的难度壁垒。
03 随机性只是幻觉？
在传统认知中，随机性是事件本身的固有属性。但在复杂性理论框架下，随机性变成了观察者和事件之间的一种关联。
密码学先驱布卢姆和米卡利提出了一个经典思想实验。同一枚被弹出的硬币，分三种场景观察：
第一种：肉眼观察，猜对概率稳定在1/2——这就是大众认知中的随机事件。
第二种：配备普通笔记本电脑，猜对概率依旧接近1/2。
第三种：普通电脑接入超级计算机，搭配高精度传感器。硬币离开手指的瞬间就能捕捉角动量、空气湿度、运动轨迹，落地前精准算出正反面——猜对概率几乎达到100%。
整个实验过程中，硬币和抛硬币的动作都没有改变。唯一变化的是观察者的计算资源。这就推翻了“随机性是事件固有属性”的传统定义：一个事件是否随机，取决于观察者的计算能力。对于算力薄弱的观察者，事件充满不确定性；对于算力极强的观察者，事件结果可以被精准预测。
基于“难题的难度等同于随机性”这个逻辑，可以推导出完整的伪随机生成逻辑。如果一个NP难问题无法被快速求解，那么对多项式时间算法而言，这个问题的答案就具备了不确定性——这就是天然的伪随机来源。阿维·维格德森与尼桑共同设计的NW生成器，就是用少量真随机种子扩展出海量伪随机比特的经典工具。
结合这套理论，学界推导出一个重要结论：如果我们认定存在部分问题需要海量计算资源才能求解，那么就可以证明P等于BPP——通俗地说，任何依靠随机数运行的高效概率算法，都能找到一套等效的高效确定性算法。随机性给算法带来的增益，并没有大家想象中那么大。
04 零知识证明：证明你知道，但不告诉你答案
1985年，戈德瓦瑟、米卡利和拉克夫正式定义了交互式证明与零知识的核心概念。1986年，阿维·维格德森联合戈德赖希、米卡利，共同证明了零知识证明的普遍性定理，为这项技术奠定了完整的理论基础。
零知识证明的核心约束很简单：在整段交互过程结束后，验证者除了能确定证明者的命题是真实的之外，无法获取任何额外信息。如果有人说自己证明了P≠NP，经过交互沟通后你完全相信他确实完成了证明，但自始至终不知道他的证明思路和步骤——这就是零知识证明想要实现的效果。
阿维用经典的图三着色问题完整演示了运行流程。证明者声称自己可以用三种颜色为一张复杂图完成着色，保证每条边连接的两个顶点颜色不同。整套协议重复几千轮，每轮验证者随机挑选一条边要求核验。如果图本身无法完成合法着色，随着核验轮次增加，验证者选中违规边的概率持续提升，作弊者蒙混过关的概率指数级下降趋近于零。每一轮颜色都会随机重排，验证者看到的只是两个互不相同的随机颜色，无法获取任何关于原始着色方案的信息——从而真正实现了零知识。
图三着色问题本身就是NP完全问题。借助NP问题之间的归约规则，任何一个NP命题都可以被转化为图三着色问题，且不改变命题的真假性。由此可以推导出零知识证明的普适性结论：所有能够用数学方法证明的命题，都可以构建对应的零知识交互式证明。这也是如今密码学、区块链、隐私计算大量使用零知识技术的理论根基。
阿维坦承，理论诞生时他曾预判零知识证明永远无法工程落地——计算开销太大。但后来的工程师们跳出了原始理论框架，设计出了更高效的协议。2025年7月，普林斯顿高等研究院的拉胡尔·伊兰戈又取得重大突破，设计出全新的零知识证明系统：全程不需要双方交互、不需要提前约定公共参数、安全性做到极致。
05 量子计算的威胁与后量子密码学
伪随机生成器、零知识证明、主流公钥密码体系——所有这些技术的底层根基都是“部分计算问题正向容易、反向困难”。一旦这类核心难题被攻破，整个技术体系都会轰然倒塌。量子计算就是威胁这套根基的最大变量。
1994年，麻省理工学院的彼得·肖尔提出肖尔算法，能够高效完成大整数分解和求解离散对数——这正是当下几乎所有公钥密码体系的安全核心。一旦成熟的通用量子计算机落地，现有主流安全体系会被全面攻破。
阿维也提醒，就算抛开量子计算机不谈，如果未来有人设计出经典的快速大整数分解算法，全世界的网络安全系统都会陷入混乱。
为了应对威胁，密码学界开启了后量子密码学研究，核心目标是寻找一类全新的数学难题——不仅经典计算机难以破解，就算有肖尔算法加持的量子计算机也无法高效攻破。目前的核心选型是格问题：高维空间中的几何难题，至今没有找到能够高效求解的量子算法。
2020年初，五位研究者联合发表的论文证明了MIP\*=RE——依靠带有量子纠缠的多证明者系统，经典验证者能够验证停机问题这类原本不可计算的问题。这篇165页的论文不仅刷新了计算复杂性理论的边界，还一举解决了纯数学领域的孔内斯嵌入猜想和量子物理领域的Tsirelson问题。复杂性理论衍生出的研究工具，正在帮助数学家和物理学家解决他们依靠自身方法长期无法突破的难题。
06 给年轻研究者的建议
阿维把理论领域的整体研究比作蚁群式协作。每年各大理论计算机科学会议产出几百篇论文，绝大多数都属于增量式推进——优化一个计算边界、改造一个经典技巧、证明一个中等规模的定理。这些看似不起眼的小进展逐步搭建起整个领域的基础设施。颠覆性的重大突破出现概率极低，并且无法提前规划、刻意追求。投身这个领域的研究者，不能把做出惊天突破当作日常目标——推动领域小幅前进，才是常态。
他着重强调：在理论计算机科学领域，建模远比单纯解题更加核心。
解题，是在已经成型的框架和定义之内完成证明和寻找算法。而建模，是从零开始创造全新的概念、框架和体系——在建模之前，连描述问题的专业词汇都不存在。NP完全性理论的创始人库克和莱文，不是解答了某一道具体的数学题，而是创造了“NP完全”这个全新的分类框架。戈德瓦瑟和米卡利不是证明了某一条定理，而是发明了“交互式证明”这套全新模型。随机性理论也同理——复杂性理论重新定义了“随机”这个概念的内涵，伪随机性、去随机化等一整个全新的研究方向都依托这个新定义诞生。
创造一个优质的基础概念、搭建一套全新的理论框架，影响力远远超过在旧体系中证明一条新定理。
对于刚入行的青年研究者，阿维建议：比起追逐当下的热门问题，找到属于自己的研究品味更加重要。多阅读不同领域的论文，尝试接触不同类型的问题，慢慢找到自己真正热爱、愿意长期投入的方向——你发自内心享受的研究工作，也恰恰是你最擅长的领域。
他还坦诚了理论研究者最真实的日常：绝大多数日子里，都是日复一日的思考却始终看不到进展。早上满怀期待开启工作，夜晚带着一无所获结束一天。如果无法享受这种持续探索、反复试错、长期沉寂的过程，只是追求快速出成果和外界关注，理论研究注定很难走下去。
“一个事件是否随机，取决于观察者的计算能力。对于算力薄弱的观察者，事件充满不确定性；对于算力极强的观察者，事件可以被精准预测。”
热门跟贴