先把最关键的一句话放在前面:截至2026年11月22日,OpenAI没有宣布证明P=NP,也没有任何一篇P=NP论文公开。这轮"OpenAI疑似证明P=NP"的说法出自没有官方出处的传闻,在社交平台上放大后被当成了既成事实。真正发生在10月底的,是OpenAI与Anthropic各自声称推翻了"指数时间假设"(ETH),而推翻ETH和证明P=NP是两回事,前者到现在也还没通过独立审查,克莱数学研究所至今仍把P vs NP列为未解决的千禧年大奖难题。哔哩哔哩知乎知乎知乎
传闻的土壤是过去两个月的连环消息。10月26日,OpenAI在GitHub的openai/math仓库公开了一篇约67页的手稿,标题是《指数时间假设是错误的》,声称其内部AI模型为3-SAT问题找到了"亚指数时间"算法,并附带机器可检查的Lean形式化证明。约8小时后,Anthropic宣布Claude用完全不同的方法独立得出了同样结论。两家论文都是GitHub上未经同行评议的预印本,ETH提出者之一的Russell Impagliazzo、Ramamohan Paturi与Ryan Williams受邀组织了公开、独立的审查,并明确声明"参与核验不等于背书"。发布方也没有把材料包装成尘埃落定的成果,而是称之为有待进一步理解的原始研究材料,邀请外部专家来核查、解释这些结果。哔哩哔哩知乎哔哩哔哩知乎微博钛媒体

推翻ETH不等于解开P=NP,差着量级
ETH是1999年前后由Impagliazzo和Paturi提出的更细的猜想:对3-SAT这类问题(给成千上万个"开关与规则",判断能否全部满足),它断言不存在2^o(n)这样的亚指数时间算法。OpenAI声称找到的恰恰是亚指数算法,正好踩在这条下界上。知乎微博
但P vs NP问的不是"比指数快多少",而是一个更狠的问题:是否存在某个固定次幂(比如n²、n¹⁰)就能解决所有规模输入的多项式时间算法。亚指数和多项式之间隔着整整一个量级——2^(√n)这类曲线比任何固定底数的指数都慢,却仍比n的任意固定次幂增长得快。所以哪怕ETH被证伪成立,也推不出P=NP。一位博主的总结点出了关键:次指数仍然可能慢得离谱,渐近优势更不等于明天的SAT求解器就起飞。微博

社区对这一区分其实相当冷静:2019年W. Gasarch对研究者的一次调查里,约88%的受访者相信P≠NP。哔哩哔哩
如果P=NP真被证明,你的密码先扛不住
要理解这件事为什么和普通人有关,得先看今天整个网络社会的安全建立在什么之上。网银支付、微信支付宝转账、网站HTTPS加密、账号密码登录,核心都是利用"求解困难、验证容易"的计算不对称性搭建而成。银行把两个数百位的超大质数相乘、公开乘积很容易,逆向拆回质数在现有算法下需要的时间长到不可行;平台存你的密码,也只存单向函数算出的"指纹"。知乎
P=NP如果成立,恰好宣告这种不对称不存在——所有"验证容易"的问题,求解也一样容易。后果按层次看:最上层是RSA、椭圆曲线等公钥体系,它们依赖的大数分解、离散对数本身就在NP里,一旦P=NP被证明并给出实际算法,现行所有依赖计算难题的传统公钥密码将会被瞬间破解。TLS证书、数字签名、区块链随之失去地基。中间层轮到密码存储和哈希:单向函数在P=NP的世界里不存在,平台数据库里存的那一串指纹不再是保护。至于"转向抗量子密码"也救不了场——格密码等候选方案依赖的同样是计算上难解的搜索问题,一样属于NP,难解性假设会被整体掀翻。知乎

真正能留下的,只有不依赖"算不动"、而依赖物理与信息的密码学——最典型的是理论上不可破的一次一密。代价是它要求密钥与明文等长、用一次换一次,几乎无法覆盖日常场景。所以普遍流传的"一旦P=NP被证明,全球密码一夜全裸"是夸张:P=NP被证明(哪怕是真的)也不等于明天上午你的支付密码就被人看穿,密钥体系会经历漫长的迁移、重签和修补;但方向上,"用计算困难性保护秘密"这件事本身会走到尽头。
AI会因此变强吗?这个方向的因果关系要倒过来想
对AI来说,P=NP的意义不在"训练模型快一点",而在它推倒了"找"与"验"之间的墙。训练模型是在天文数字的参数空间里"找"一组能解释数据的参数,自动推理是在指数级增长的搜索空间里"找"一条验证器几秒就能检查的证明链——今天AI的很多"笨办法",海量采样、暴力搜索、人工标注,本质都在为"找比验难"付账。如果P=NP成立并附带实用算法,机器寻找最优解、最优模型、最短证明的成本会降到与验证一次差不多,AI证明定理、设计分子、解优化难题都可能变成"检查答案"级别的体力活。这一"找与验"的不对称,哥德尔1956年写给冯·诺依曼的信里就已经触及。哔哩哔哩

反过来看,即便最终证明P≠NP,AI也不会就此止步:人类今天就在用启发式和算力硬啃NP难题,AI只是把这件事做得更快。真正的问题不是P等不等于NP,而是理解的速度跟不上答案生产的速度——陶哲轩评价这轮AI成果时给出的正是这种担忧:我们不想只让黑箱给出答案,自己却不知道答案从何而来。钛媒体
所以眼下对普通人,两个判断可以带走:你的密码此刻仍然是安全的,推翻ETH并不等于自动攻破现代加密,强密码加双重验证照常有效。需要认真担心的,是"P=NP被真正证明且给出实用算法"的那一天,而那一天目前并不存在,值得盯的信号也很简单:独立审查的结论,以及克莱研究所P vs NP那一页的状态。哔哩哔哩
当前文章无评论,是时候发表评论了