截至2026年11月22日,P=NP既没有被证明,也没有被证伪,OpenAI从未正式宣称解决这道千禧年难题。这轮讨论来自数学界过去48小时的新闻:11月21日,Lean与Mathlib社区认证了Anthropic数学家Levent Alpöge与Claude完成的黎曼猜想形式化证明;次日,GPT-6 Astra Pro交出一份核心推导不到6页的有限域黎曼猜想新证明。千禧年难题接连被破,“OpenAI已经解决P=NP”的说法随即在社区传开——这则传闻没有任何官方公告或论文背书。
OpenAI在P与NP问题上的真实一步,是10月26日迈出的:它的内部模型给出3-SAT的亚指数时间算法,推翻了立论27年的指数时间假设(ETH)。这是实打实的进展,但亚指数离多项式仍然不是一回事,两者之间的距离,在复杂性理论里有明确的标尺。知乎微博
一、推倒的那堵墙,和划清的那条线
2026年10月26日的官方公告列出了三项由内部模型产生的结果:调和分析中的局部光滑猜想、计算复杂性中ETH不成立、规范场论的严格存在性证明。几小时后,Anthropic发布了一篇由内部Claude模型独立完成的反驳论文,得出了完全相同的结论。两家都附上可逐行核对的Lean形式化。按论文自述,OpenAI的内部模型在10月16日得到证明,次日完成Lean形式化。微博
为确认含金量,OpenAI请来1999年提出ETH的本尊Impagliazzo和Paturi,加上MIT教授Ryan Williams牵头公开审查,三人不签保密协议、不取报酬。三位审查人在公开信中写道,“我们的参与不应被视为对该结论的认证”。知乎
过去27年没人证明ETH对错,研究者却默认它成立,图论、数据库、计算生物学里几百篇条件性下界结论都压在这块地基上。更值得注意的是两家公司发布时主动划的线:结果不直接涉及P与NP问题,也不产生实用算法。Lance Fortnow的判断是他没有亲自验证,但可以比较放心地认为ETH“完蛋了”。压在它上面的结论失去的是前提,需要换依据,而不是被证伪。微博知乎知乎
二、从亚指数到多项式,中间还隔着十万八千里
开关谜题(3-SAT)正是所有“好检查、难计算”难题的总代表:所有NP类问题都能翻译成它,因此P是否等于NP,归结为这道谜题能不能被“真正算得快”。此前最好的确定性算法约1.328ⁿ,差不多每加两三个变量工作量翻一倍。ETH赌的就是“翻倍间隔”有永远突破不了的上限。新算法证伪了这个断言:间隔确实随规模增长,只是长得极慢——这就是亚指数时间。微博知乎
把解题速度排成三级台阶:指数级、亚指数级(AI现在所在)、多项式级(证明P=NP需要)。100万个变量时,亚指数只比指数多出让工作量翻倍寥寥几个开关,多项式却要一口气多几十万才翻一倍。Anthropic自己算了新旧速度交叉的实际规模,论文直言这一结果对实际求解什么也说明不了。墙确实裂了,但裂在现实中没人走得到的高度;对每天和3-SAT打交道的人来说,墙依然立着。微博知乎

三、证“P=NP”和证“P≠NP”,根本不是同一种活
标题里的“证明P=NP”,恰恰不是主流预期的方向:学界多数相信P≠NP更可能成立。连ETH的著名怀疑者Williams,此前也只是给ETH为真押了约70%的概率。两个方向要的数学对象完全不同:证P=NP只需一个3-SAT的多项式时间算法,属于构造性任务;证P≠NP却要对所有可能的算法证明“都快不了”,而标准理论已经找出三道横在证明路上的障碍:相对化、自然证明、代数化。三道壁垒意味着成片的证明技术被排除在外,至今仍没有公认的替代框架。微博知乎知乎
ETH倒下确实动摇了不少直觉:Williams说每个计算机科学家都该给“P=NP可能成立”多留一点心理空间,但在他看来,所有好检查的题都能真正算得快,依然像“天上掉馅饼的美事,美好得不太可能成真”。微博
四、黎曼走通的路,P vs NP 暂时用不上
过去几天被破的记录有一个共同结构:命题早已定义清楚,证明要在成熟框架内被“找出来”,最后交给Lean逐行核验。黎曼猜想在AI手里也走过“进展不等于完成”的阶段:今年8月,Claude把可严格证明位于临界线上的零点比例下界从约41.6%提高到67.2%,这不意味着黎曼猜想完成了67.2%。知乎
直到11月21日,Lean与Mathlib社区发布联合声明,对Levent Alpöge与Claude给出的形式化证明“完全有信心”,并确认它证明的就是Mathlib中经过审查的黎曼猜想。宣布不等于证明,认证才算数。知乎
OpenAI这边的回应是另一条时间线。GPT-6 Astra Pro在24小时内拿出有限域黎曼猜想的新证明,核心推导不到6页,而1974年Deligne的原始论证超过150页。推导全程无人参与,靠的是在Deligne定理的现成框架里搜索一条更短的路。知乎
但这些成绩全部发生在有现成框架可搜索的问题上:命题早已定义清楚,框架成熟,证明可以在体系内被找到、由机器核验。反观P与NP,缺的正是这样一个能刻画搜索难度的框架。AI的“搜索—验证”打法,在这里暂时没有落脚点。知乎

五、接下来该盯什么
最该等的,是10月启动的ETH公开审查结论:截至10月27日,OpenAI公布的三项结果都还没有经过独立的同行确认。此后近一个月未见最终裁定公布。另一个参照是误读本身如何产生:11月上旬,OpenAI模型证出Landau-Siegel零点不存在、一口气放出722篇数学手稿,被部分报道牵到P≠NP讨论里,但专家当时的口径很清楚——P与NP尚未解决,证明验证与可读性仍是短板。11月21日黎曼认证刷屏后,知乎上“据说openai已经解决了p=np”的回答也只有5个赞同,没有任何可定位的原始公告。知乎微博知乎
节奏仍在变快:OpenAI11月18日发布第二份研究加速报告《研究加速·锯齿状前沿》,自家coding agent在2到4小时人类工作量任务上的零干预成功率,已从约三成升至46%。把这套速度外推到千禧年难题,是“2027年AI会证伪P=NP吗”这类讨论的来源,但那是推测不是结果。真出现P vs NP宣布时,模板大概率与黎曼相同:论文、Lean形式化、独立社区认证缺一不可;在此之前,答案只有一句话——OpenAI离证明P=NP还有整个复杂性理论的距离,目前迈出的最大一步,是亚指数。知乎

当前文章无评论,是时候发表评论了