Exponential Time Hypothesis (ETH)
搜索文档
OpenAI掀翻计算机科学30年基石,还解决了挂谷猜想
机器之心· 2026-10-27 15:00
文章核心观点 - OpenAI于10月26日宣布在数学、计算机科学和物理学三个领域取得新成果,包括证明所有维度下的局部光滑化猜想、证伪指数时间假设(ETH)、为四维量子场论建立严格数学存在性证明,总裁Greg Brockman称其为三项重大科学发现 [3] - 三项成果分别对应三种不同的发布与审查安排:数学部分直接公开让社区自行组织研究,计算机科学部分公开证明同时邀请ETH原始提出者组织独立审查,物理部分先交给专家团队整理后再决定如何发表 [36] - 文章核心关切在于:当AI能够在短时间内生成大量前沿研究成果,科学界该如何消化这些新知识,如何将AI结论转化为真正可以理解、验证和继续发展的知识 [38][40] 指数时间假设(ETH)的证伪 - ETH由Russell Impagliazzo、Ramamohan Paturi和Francis Zane于1990年代末提出,核心观点是不存在一种能够在亚指数时间内解决所有3-SAT问题的算法,即无法把最坏情况运行时间降到2^{o(n)}量级 [9][11] - 此后近30年,ETH成为理论计算机科学的重要基础假设,已有数百篇研究论文依赖这一假设建立条件性困难性结论,涉及图算法、数据库查询和计算生物学等领域 [11] - OpenAI内部模型构造了一种确定性算法,对于固定宽度的CNF布尔公式,不仅能判断是否存在满足条件的赋值,还能精确计算满足条件的赋值数量 [12] - 对于子句数量与变量数量成比例的相关问题,公司给出了形如2^{O(n/√log n)}的运行时间界(略去多项式因子),属于亚指数时间,若证明成立即意味着ETH被证伪 [13][14] - 模型在10月16日生成ETH的自然语言反证,次日完成Lean形式化,并于10月26日正式公布结果 [16] - OpenAI邀请加州大学圣迭戈分校的Impagliazzo、Paturi以及MIT的Ryan Williams组织外部研究团队,前两人正是ETH的原始提出者,Williams长期研究算法与计算复杂性下界 [15] 局部光滑化猜想与挂谷问题 - 新成果首先瞄准数学家Christopher Sogge在1991年提出的局部光滑化猜想,研究波在传播过程中如何在时间平均意义上获得额外规则性 [21][22] - 2019年Larry Guth、王虹和张瑞祥证明了二维空间下的局部光滑化猜想,OpenAI现在宣称模型找到一种新的辅助偏微分方程,借此把证明推进到所有空间维度 [23] - 按照公司论述,这一结果进一步解决了所有维度下的挂谷猜想与Stein限制猜想 [23] - 此前在722篇手稿中,第074号成果族声称证明三维挂谷极大猜想和四维挂谷维数猜想,但当时尚无对应的Lean形式化证明;2025年王虹和Joshua Zahl解决了三维挂谷集合猜想 [20] - 模型在10月18日得到证明,10月19日完成Lean形式化,自然语言手稿和形式化证明已公开;与ETH不同,数学部分未指定先行审查小组,研究者直接进入公开材料自行组织解释和复核 [24] 四维量子场论与杨—米尔斯存在性 - 量子色动力学(QCD)描述夸克和胶子之间的强相互作用,相关计算和实验构成现代粒子物理的重要支柱,但将其严格构造成满足数学公理的量子场论长期面临巨大数学困难 [28][29] - OpenAI声称内部模型沿着数学物理学家Tadeusz Balaban的构造性量子场论研究路线,建立了某些包含规范场与费米子的四维相互作用量子场论的严格存在性证明,涉及QCD以及容纳标准模型规范场和费米子的一种统一扩展 [30] - 工作还包含纯Yang–Mills理论的存在性证明;2000年克雷数学研究所将杨—米尔斯存在性与质量间隙列为七大千禧年数学难题之一,公司此次宣布的部分是存在性,并未宣布解决质量间隙 [31] - 2004年诺贝尔物理学奖得主David Gross将牵头工作组,成员包括Michael Douglas、Arthur Jaffe、Igor Klebanov和Nikita Nekrasov;Gross因渐近自由相关工作获奖,Jaffe曾与Edward Witten共同撰写杨—米尔斯千禧年难题的正式表述 [32] - 模型早在9月9日就生成杨—米尔斯存在性证明,9月18日生成QCD相关证明,由于材料复杂庞大,公司一直等到10月16日完成杨—米尔斯存在性的Lean形式化才推进外部合作 [32] - 物理工作组选择先整理、理解并撰写自己的研究文本,暂时不公开AI生成的原始证明 [32] 成果发布机制与学术界协作 - 10月6日公布722篇手稿时,公司采用集中公开模式,将论文、证明文件、结果目录和部分模型推理摘要一起放进GitHub,手稿分属372个成果族、17个研究方向 [5][34] - 此前那批手稿公开后,有三份因证明中的符号错误被撤回;即使有Lean形式化,学术界仍需弄清形式化定理是否准确对应原来的猜想,以及证明引入了哪些可迁移的新方法 [34] - 公司将AI产物定位为原始研究数据,把产生证明与形成科学理解分开:前者可由AI先行完成,后者需要研究者复核论证、重写解释、追溯已有工作、判断贡献 [35] - 公司提出几条合作原则:外部成员自愿独立参与,不签署保密协议,不因模型发现而替公司争取学术署名,应因自己完成的解释、证明整理和后续研究获得认可 [37] - 公司承诺支持独立审查,并此前宣布向Simons Foundation的相关计划投入500万美元,用于研讨会、学术会议和研究项目 [37] - 直接公开证明可让更多研究者立即参与,但庞大审查工作需由社区自行承担;先交给专家团队能集中力量整理复杂成果,却也让部分人比其他研究者更早接触材料 [38]