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

如果P=NP真的被证明,普通人的生活可能有哪些变化

如果P=NP真的被证明,且证明附带着一个真正跑得起来的算法,普通人的生活会在两件事上同时被改写:一边是守护你全部线上生活的"锁"——支付、密码、聊天记录、数字资产——一夜之间变成摆设;另一边是那些过去只能"差不多就行"的问题——快递路线、班次排布、货物装箱、新药分子筛选——突然都有了通向最优解的捷径。但"世界末日"和"立刻天堂"两种流行说法都漏掉了同一个前提:“P=NP被证明"和"给出一个能用的算法”,是距离悬殊的两件事。今天这道1971年提出的老题之所以突然冲上热榜,恰恰是因为AI把人类推到了一道从未有近的门口。

一个1971年的老问题,为什么突然挤上热榜

直接导火索在2026年10月底。OpenAI在官方公告中声称,其内部AI系统得到了足以反驳指数时间假说的算法和证明——GitHub上的手稿标注日期是10月25日,自然语言证明产生于10月16日,Lean形式化于10月17日完成,10月26日公开发布,而OpenAI同时宣布在数学、计算机科学、物理三个领域取得突破。知乎知乎

如果P=NP真的被证明,普通人的生活可能有哪些变化

更有戏剧性的是,就在OpenAI发布结果几小时后,竞争对手Anthropic也宣布自家模型在同一天找到了几乎相同的ETH证明,只是走了不同的技术路线。所谓指数时间假说(ETH),是1999年前后由Impagliazzo和Paturi提出的假设,主张对3-SAT这样的典型组合问题,计算机不可能把最坏情况下的运行时间降到真正的亚指数级。也因此,"OpenAI解决了P vs NP"的说法被专门指出是误读——即使ETH最终被证实为假,问题仍可能是P=NP,也可能是P≠NP,比固定底数指数更快的算法并不等于多项式时间算法。知乎哔哩哔哩知乎

但这项声称至今仍是未经同行评议的预印本:Russell Impagliazzo、Ramamohan Paturi和Ryan Williams组织的独立开放审查已经启动,而三位学者明确声明,他们的参与不应被视为对该声称的认证。机器检查通过Lean形式化证明,也不自动保证被形式化的陈述就是原来那条复杂性猜想——这正是这项声称需要比一般研究更严苛公开检验的原因。知乎

另一条刷屏的消息也在推波助澜:有数学家称与AI合作证明了黎曼猜想,证明稿超过25万页,MIT团队发布的验证报告也显示超17万个模块全部编译无错。千禧年难题接连被AI叩响,剩下堡垒里最硬的那一道,就成了热搜上的主角。知乎知乎

先把底数说清楚。P对NP问题自1971年被正式提出以来,争议已经困扰全球科学家半个世纪;2000年,它被克雷数学研究所列为七大千禧年难题之一,任何一道难题被完整严谨地证明,解题者就能获得100万美元奖金,而二十多年过去,七大难题里只有庞加莱猜想被成功破解。截至现在,它仍未被解决;绝大多数研究者仍然相信,答案是P≠NP——有讨论就直言,证明出P≠NP无非是把大家默认了半个世纪的假设变成定理。知乎知乎知乎

先用数独看懂:什么叫"验证容易、求解困难"

P类问题指有快速解法的问题,NP类问题指答案一旦给出就能快速核验的问题。数独是最直观的标本:想要从零开始填出一张百格千格巨型数独且不出差错,用当下最顶尖的超级计算机暴力枚举,耗时足以跨越千万年;但反过来,只要有人递给你一份填好的完整答案,逐行逐列逐宫核对几分钟就能确认对错。你能"一秒验对"的东西,未必能"一小时做出"——P=NP断言的正是:凡是验证容易的问题,求解也一定有捷径。知乎

如果P=NP真的被证明,普通人的生活可能有哪些变化

真正让这个等式牵动全局的,是上世纪七十年代的一条定理链:Cook在1971年建立了库克—莱文定理的核心结果,Levin独立发展出完备性理论,随后Karp把完备性思想扩展到21个自然组合问题。这意味着NP类问题"同气连枝"——只要任何一个NP完全问题(比如3-SAT)找到多项式时间算法,所有NP问题就全部找到。快递最优路线、排班、装箱、芯片布线、蛋白质结构搜索,这些你生活里真实存在的难题,会被一并解锁。知乎

真正的分水岭:证明长什么样,你就过哪种日子

这是多数同题文章跳过的一环。复杂性理论里"多项式"只是一个理论上的效率界:n的一千次方也是多项式,对任何现实规模的输入仍然不可行。所以P=NP的证明至少有三种形态,普通人的命运完全不同。知乎

第一种,存在性证明或高次多项式证明。NP=P并没有承诺这是一个计算设备能接受的低次多项式,甚至没有承诺算法可以被构造性地显式写出来——理论上已知的莱文式通用搜索自带离谱的常数项,实用价值接近于零。这种情况下,学界震动、密码学家连夜检查自家假设的细节,但你的快递不会变快,银行照常运转——冲击停留在观念层面。知乎

第二种,给出可构造但工程上昂贵的算法:影响真实到来,但要经过代码实现、芯片适配、系统集成,以年为单位慢慢渗透。第三种,才是头条党默认的那种:低次多项式、常数友好、直接能跑。下面讲的三大变化,只有第三种才成立。

变化一:数字世界的锁,一夜之间集体失效

现代互联网的安全大厦建立在一类叫"单向函数"的地基上——正向算得快、逆向算不动,网银支付、HTTPS、端到端加密聊天、区块链钱包全部靠它。直觉很简单:给一对明文和密文,"找回密钥"就是典型的验证容易、求解困难——逐把试钥匙,一秒就能判断开不开,但试遍要亿万年。有讨论对此的判断是:一旦P=NP并给出实际算法,现行所有依赖计算难题的传统公钥密码将会被瞬间破解。知乎

需要一点精确性以免恐慌失焦:整数分解本身并非已知的NP完全问题,RSA还额外依赖大整数分解的平均情况困难性等更具体的假设,"P=NP瞬间黑进所有网站"其实是夸张。但只要单向函数的存在性被P=NP堵死,正在部署的抗量子密码方案同样依赖计算困难假设而非物理定律,整套建立在"算不动"之上的体系都撑不住。知乎

普通人感受到的不会是世界末日式的断网,而是一段危险的过渡期:历史数据被重新解密,几年前加密的聊天记录、医疗档案、企业文件可能集体透明化;银行、支付、政务系统被迫在几年内迁移到少数还站得住的方案——一次一密(无条件安全,但密钥要和信息一样长、用完即废、需要事先运送)、基于物理定律的密钥分发,以及重新重视线下凭证。数字资产的持有逻辑也会被重估:依赖算力与私钥保护的玩法,在一台"万能配钥机"面前归零。

变化二:生活的"最优解"突然有了捷径

这一面是正向的。有科普文章概括得很直接:一旦有实用算法,物流交通、能源制造能瞬间算出绝对最优解,医药领域能快速推演蛋白质结构、攻克疑难病症,新药研发效率暴涨百倍。今天这些领域都在用启发式算法换"足够好",成本和最优之间永远隔着一截浪费;万能算法把"找最优"降级成"抄答案",配送里程、空驶率、电网损耗会被进一步压低。知乎

但也要打两针预防针:一是这些行业本来就逼近最优不差,收益是把最后的10%挤出来,不会让运费瞬间归零;二是算法解决"怎么找到最优",不解决"什么是最优"——目标函数、约束条件、数据质量仍要人来定义,找错方向的捷径只会更快抵达错误的终点。

变化三:"能验证"的东西不再稀缺,"能定义"的东西才值钱

P=NP还有更少被讨论的一层冲击:有讨论指出,证明P=NP"自然就会包含一个方法,通用的方法"。如果验证一篇证明是机械的,那么寻找证明本身也将是机械的:数学定理发现、程序正确性检查、逻辑推理这些"天才的自留地"会被自动化工具批量占领。同样的逻辑外溢到创作和研发——任何有明确验收标准的结果(有bug就能复现、不合规就能判负)都能被机器反向生成,人类的溢价从"做出来"转移到"提出值得验证的标准"。机器学习的全局参数搜索也会从"运气好才收敛"变成可精确求解的问题,AI能力再上一个台阶,反过来加速前两个变化落地。知乎

对就业市场的含义不难推导:最先贬值的是"靠搜索和试错吃饭"的岗位——初级审计、基础排产、原型测试、部分算法调参;最难替代的是定义问题、承担责任、给出品味的人。

如果最终被证明的是P≠NP

同样值得说,因为这是目前多数研究者相信的方向。有观点总结得很干脆:证明P≠NP,密码学的人可以松一口气。它意味着"难题天生没有捷径"成为盖棺定论,加密体系获得数学层面的理论保障,优化领域继续用近似与启发式过安稳日子。对普通人来说,这是"没有新闻"的一天——你现有的支付、密码和聊天记录继续安全;真正的地震发生在学术界:过去二十多年建立在ETH等假设上的条件性下界网络需要重写。知乎知乎

现在该焦虑什么,可以观察什么

先说不必的部分:截至今天,你的支付加密仍在照常运转——有讨论特意提醒过,P=NP被证伪了吗?没有,AES加密已经基于P≠NP运作了很多年。值得留意的有三个信号:其一,针对ETH预印本的那场独立开放审查的最终结论,以及Lean形式化陈述是否精确对应原猜想。其二,任何真正的P=NP声称都会先以公开手稿出现,并经历数月甚至数年的同行挑战——2010年Deolalikar声称证明P≠NP、最终被找出关键缺陷,就是最近的历史教训。其三,看证明给出的算法形态:有没有可运行的代码,多项式的次数和常数是多少。知乎知乎

这道题真正迷人的地方在于:无论最终答案是哪个,普通人都将第一次确切知道一件过去只能凭经验相信的事——我们习以为常的数字文明,究竟建在哪一块基石上。

评论

评论区空态插画

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