什么值得买App下载 App ›
连续签到专享现金活动

网传AI证明P=NP是真的吗?目前学界确认到哪一步

网传"AI证明P=NP"不是真的——截至11月22日,任何机构关于P=NP的官方声明或论文都查不到。克雷数学研究所的P与NP问题页面至今仍把这道题列为未解决的千禧年难题。哔哩哔哩知乎知乎

传闻之所以刷屏,是因为过去一个月AI在数学领域确实连环放出了几个大新闻。三个各自独立、各自还没有定论的真实事件,在传播中被捏合成了同一句话。

三个事件,没有一个等于"证明了P=NP"

第一个是10月26日的"OpenAI证伪ETH"。OpenAI公告称,其内部AI系统得到了一项足以反驳指数时间假设(ETH)的算法和证明,手稿题为《指数时间假设是错误的》。Anthropic随后表示,自家模型几乎同一天沿不同路线找到了相同的证明。ETH主张3-SAT最坏情况下不可能降到真正的亚指数级,过去大量"某问题无法更快"的条件性下界都拿它当前提,它一旦倒下牵连很广;但"证伪ETH"和"证明P=NP"是两个命题——一个比固定底数指数算法渐近更快的算法,不等于一个多项式时间算法,ETH即使被证伪,P与NP仍然可能相等也可能不相等。知乎知乎

截至资料核查,这份手稿仍只是GitHub上的非同行评议预印本;Russell Impagliazzo、Ramamohan Paturi和Ryan Williams组织了独立开放审查,并明确声明:他们的参与不应被视为对该声称的认证。知乎

网传AI证明P=NP是真的吗?目前学界确认到哪一步

第二个是11月20日的黎曼猜想证明。Anthropic数学家Levent Alpöge宣称借助Claude证明了黎曼猜想,他发布的Lean代码有17374215行,其中15531759行非空白,作者称转换为人类可读文本超过25万页,范围还包括狄利克雷L函数的广义黎曼猜想。11月21日,Lean与Mathlib社区发布联合声明,正式确认黎曼猜想的命题及其证明均正确。MIT的Andrew Sutherland等学者报告,目前记录中175,187个模块已编译通过,也逐个接受了Lean内核重放,独立实现的检查器接受了导出的证明,公理审计确认五个主要定理只依赖Lean的三条基础逻辑公理,顶层定理直接引用Mathlib里已有的黎曼猜想定义——"把题目偷偷改成弱命题"的常见担忧,就此有了可检查的回应。知乎知乎知乎

机器一路绿灯,人却还没点头。牛津的James Maynard认为证明很可能是对的,“我有98%或99%的把握”,同一句话里他补了限定:Lean是强大的证明检查器,必须稍微谨慎,确保Lean验证的确实是你想要证明的那个东西。克雷数学研究所的题目页面上,黎曼猜想目前仍列在未解决问题中。知乎知乎

陶哲轩在博客给出的初步判断是,从非常初步的分析看,这份证明似乎用上了朗兰兹纲领和算术几何领域的现代前沿成果;数学界要梳理其中的核心思路、验证正确性,还需要一段时间。而黎曼猜想无论成不成立,都不蕴含P=NP:黎曼猜想为真,并不会自动意味着P=NP,也不会自动降低破解RSA加密的难度。知乎知乎

第三个是11月21日起流传的"Anthropic在MIT闭门会议上称质因数分解属于P"。这条说法至今没有任何可核查的一手来源,属于未核验线索,但它恰恰是点燃"AI要破密码了"恐慌的最后一根稻草——把质因数分解和NP难混为一谈,再顺势推出"那就是P=NP了"。把这三件事放回各自的位置,传闻就失去了立足点:没有任何一家机构宣布、也没有任何一份经得起检验的材料声称证明了P=NP。知乎

P=NP本身,学界卡在哪一步

P与NP问的是一件朴素的事:凡是答案能快速核验的问题,能不能也快速求解?数独填好的答案一眼能查对错,但从零开始解一个巨型数独要付出天文数字般的时间。按夜行的归纳,P vs NP问的就是,能不能找到一个办法,对所有规模的这类输入都判断正确,而且最坏情况下的耗时能被输入长度的某个固定次幂压住。知乎

网传AI证明P=NP是真的吗?目前学界确认到哪一步

半个世纪过去,学界的处境可以概括为:共识明确,方法匮乏。按2019年发表的SIGACT News同行调查,约88%的受访研究者相信P≠NP。真正难的不是站队,而是证明——相对化、自然证明和代数化障碍告诉我们,许多看似理所当然的证明路径无法走到终点。复杂性学者Lance Fortnow 11月撰文,他已经不去猜AI下一个会证明什么了,但仍认为P vs NP需要新的方法。哔哩哔哩知乎知乎

历史也反复提醒"宣称"和"证明"之间的距离。2010年8月,惠普研究员Vinay Deolalikar公开了一份长篇手稿,声称解决P vs NP,专家们很快指出关键缺陷。今年6月,T.S. Arthanari宣布证明了P=NP并通过Lean 4验证,结果被人扒出来证明的是同义反复——他用的不是标准定义。这正是形式化验证的边界:内核能保证每一步推导合法,却不保证你写进机器的题目就是原本那个问题。黎曼猜想的这次核验之所以分量更重,恰恰因为社区专门审计了"陈述是否就是黎曼猜想本身"——这套标准,目前没有任何一个P=NP声称经得起。知乎知乎

网传AI证明P=NP是真的吗?目前学界确认到哪一步

对你的密码意味着什么

这是传闻里最需要降温的部分。即便OpenAI的ETH算法最终通过独立审查,它带来的首先是精细复杂性研究领域重写条件性下界,而不是你的支付密码失效:亚指数不等于多项式,最坏情况不等于密码学面对的平均情况,理论算法里还可能有现实规模见不到优势的隐藏常数。目前没有证据表明这份未经独立确认的ETH反例带来即时、大规模的密码系统破坏,比特币、RSA、椭圆曲线密码或现代加密协议并不会因此立刻失效。真正要担心加密体系崩塌,条件是出现可运行、多项式时间的NP完全问题算法——那一步,学界今天还远远没有确认到。知乎

值得持续盯住的三个信号:Impagliazzo等人对ETH手稿的独立审查结论;Alpöge承诺的"人类可读版"证明以及围绕它的消化进度;还有克雷数学研究所官网对P与NP问题状态的标注。三者都还没有变化,所以结论维持不变——截至11月22日,AI没有证明P=NP,它离"被证明"还隔着方法上的空白;这场传闻真正的起点,是一份通过了机器核验、但人类还没读完的黎曼猜想证明。哔哩哔哩知乎

评论

评论区空态插画

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