AI模型挑战指数时间假设（ETH）的成果 · 话题榜 · TwKit

@Phoenixyin13

不想传播焦虑，但这次我无话可说。 今年科学界最大的新闻，没有之一。OpenAI 的内部 AI 模型自己做出了三个科学难题的成果。我用我自己的理解说一下。 第一，Kakeya 猜想。这个问题研究波聚焦时会怎样。原来的猜想我记得是说最极端的聚焦只会持续很短时间。人类以前只在低维度证明过，OpenAI 说它的模型证明了所有维度的情况，因此顺带解决了 Kakeya 猜想和 Stein 限制猜想。纯逆天。 第二，指数时间假说 ETH 被推翻。这个太难以置信了。ETH 好像是说有一类逻辑难题不可能被比暴力穷举快很多地解决。而之前学界普遍相信它成立，几百篇论文都以它为前提，现在 AI 却证明它是错的。 这个太他喵逆天了，因为我之前是研究过一段时间理论计算机的。这几十年ETH几乎被当成公理在用。很多论文的结论都写成假设 ETH 成立，那么某某问题不可能在多少时间内解决。现在地基没了，这些不可能，全都要打问号。 最让我感觉匪夷所思的是 AI 证明的方式。据 Lean 证明的说明文档，它给出的是一个确定性算法，应该是对固定宽度的 k-CNF 公式，它能在亚指数时间、多项式空间内精确数出所有满足的赋值。但是，懂行的人应该都知道“数出有多少个解”通常比“判断有没有解”难得多，它连更难的那个都做到了，所以 ETH 只是顺带被推翻。 第三，杨-米尔斯、量子色动力学。AI 应该是给出了一套严格的数学证明，证明描述强核力的理论在数学上确实成立，其中包括纯杨-米尔斯理论的存在性，这是千禧年七大难题之一的一部分。我不太了解，但是只是知道一些浅层的理论，就不评论了。 最让我恐惧和惊骇的是第二个。今天晚上我看了又看，感觉这是地震级别。如果最终确认无误，这会是 AI 第一次独立推翻一个被广泛相信的核心猜想。说它是一个时代的分界点，也毫不夸张。 如果这三个都核查通过，这代表 AI 第一次在多个顶尖领域独立解决了几十年没人能解决的难题，影响史无前例。

@MaxForAI

大家可能不太理解，今天早上OpenAI宣布ETH被证伪，到底是一件多么震撼的事情。 这么说吧，今天早上我的算法群里都在讨论这件事。 ETH，全称指数时间假设，是理论计算机科学中一个极其重要的基础假设。 这个猜想提出已经二十多年了，过去有数百篇论文以 ETH 成立为前提，去研究各种计算问题的复杂性下界。 从图论、组合优化，到数据库和计算生物学，很多研究都建立在这个假设之上。 结果现在， @OpenAI 的一个内部模型突然声称，它证明了 ETH是错的。 群里还有个哥们儿，他之前写的一篇论文就是以 ETH 成立为前提的。 现在这个前提可能直接没了，论文的结论要重新审视。 你想象一下，你花了几年时间研究一个问题，写论文、做证明，甚至一个领域的学者围绕这个假设研究了二十多年（比如图里这个教授）。 结果有一天，一个AI模型告诉你，大家一直以来相信的前提可能就是错的。 更离谱的是，OpenAI已经公开了论文和Lean形式化证明，还邀请了当年提出 ETH 的两位研究者，亲自参与这项结果的独立审查。 当然，目前还不能说ETH已经被正式证伪，但如果这个证明最终成立，它对理论计算机科学的影响可能会持续很多年（不亚于P=NP这个问题）。 大量依赖ETH的条件性研究结论，都需要重新评估了。

@Phoenixyin13

接下来就看一件事，PNP。 如果不远的未来AI已经逆天到可以成功证明 P=NP，而且算法真的实用，由于大部分加密都依赖验证容易破解很难，P=NP 意味着破解也能变容易。银行、HTTPS、加密货币，这些玩意全部得推倒重来。 而且优化问题会被打通。 现在困扰的排班、物流路线、芯片设计、蛋白质折叠这类问题，都能速速直接算出最优解。 数学研究本身被自动化，陶哲轩所说的数学工业时代必然进入高潮。因为检查一个证明是容易的，P=NP 意味着找到证明也会变得高效。很多猜想能让机器直接搜出证明。想想吧，冯诺伊曼也顶不住啊。 今天，我真的沉痛地思考了很久。人类一直默认欣赏一首好曲子比写出它容易，看懂一个证明比想出它容易，认出好设计比设计出来容易。人类对天才和创造力的理解，很大程度上就建立在这个差距上。 而P=NP 在数学上等于说，至少对一大类问题，这个差距并不存在。因为只要能高效判断什么是好答案，就能高效找到它。所以有学者说，如果 P=NP，这个世界上，就不存在本质上的灵光一现： 创造力，可以被机械化。 创造力，可以被机械化。 创造力，可以被机械化。 我连说三遍，是想强调，这件事会对人类一直引以为傲的创造性产生深刻的打击。

@ktwu01

OpenAI 刚刚挑战了计算机科学界 25 年的一个基本信念。 这可能是 AI 科研史上最重要的突破之一。 2026 年 10 月 17 日，OpenAI 发布了一篇论文，标题只有一句话： 《The Exponential Time Hypothesis Is False》 翻译过来就是： 「指数时间假说是错的。」 你可能不知道这意味着什么。 但如果这篇论文最终被证实，它可能会改变我们对计算机能力极限的理解。 我用 16 岁高中生也能听懂的方式解释一下。 先想象一个游戏 你面前有 30 个开关。 每个开关只有两种状态：开或关。 你需要找到一组开关组合，同时满足几百条规则。 问题是： 30 个开关，总共有多少种组合？ 答案是： 2³⁰ = 10.7 亿种。 如果有 100 个开关呢？ 组合数量就变成一个天文数字。 这就是计算机科学中的经典难题：SAT（布尔可满足性问题）。 过去几十年，科学家普遍相信一个假说： 对于某些 SAT 问题，不管你的算法多聪明，最坏情况下，计算时间都无法避免指数级增长。 这个假说叫 ETH，指数时间假说。 它是计算复杂性理论的重要基础。 然后，OpenAI 的 AI 做了一件惊人的事 它提出了一种全新的算法。 不仅能够判断这些开关有没有满足规则的组合。 还能精确计算到底有多少种合法组合。 更重要的是： 理论上，它的运行时间增长速度突破了 ETH 所假设的指数级下界。 数学家称之为「亚指数时间」。 简单理解： 以前大家以为，你不可能绕开的一堵墙，现在 AI 声称找到了一条路。 而且 OpenAI 还发布了使用 Lean 数学证明系统进行形式化验证的代码。 这是不是意味着所有难题都能秒解？ 不是。 这里有两个非常重要的区别： 第一，亚指数时间不等于几秒钟解决问题。面对足够大的问题，算法仍然可能非常慢。 第二，这也不意味着著名的 P vs NP 难题已经解决。 真正的突破不是电脑突然快了 100 万倍，而是我们对计算难度的理论认知可能需要被重新审视。 目前，OpenAI 已公布论文和形式化证明，独立专家仍在审查这一结果。 我觉得最震撼的，其实不是算法本身。 而是一个更大的变化： 过去，我们把 AI 当成回答问题的工具。 后来，它开始帮助人类写代码、做实验、寻找规律。 现在，它开始提出可能改变计算机科学基础理论的证明。 AI 正在从使用人类已知知识，走向帮助人类发现未知知识。 当然，这次研究能否完全经受住学术界的检验，还需要时间。 但一个值得所有年轻人思考的问题已经出现： 如果 AI 不仅能回答考试题，还能挑战写在教科书里的理论，那么未来 10 年，我们应该学会什么？ 我认为，答案可能不再只是「学会解决问题」。 而是： 学会提出真正值得解决的问题。 你怎么看？

@lidangzzz

这是21世纪人类文明最悲痛的一天，也是18岁的我最悲痛的一天，悲痛到我什么话都说不出来了。 数学家们反复辱骂，说AI无法创造任何新的知识，而今天OpenAI已经精美绝妙构造出了面向P=NP伟大的进步，把ETH这个计算机乃至全人类最重要的共识彻底撕碎。 震惊，绝望，恐惧，无奈，撕心裂肺，彻底认输。

@Phoenixyin13

我不知道大家怎么理解ETH这件事。 我还认识一些TCS领域的人。有些老教授的此刻正在经历精神世界乃至大半生心血被时代巨浪瞬间重塑的极限冲击，这样说也毫不为过。自从数十年前，这一假设被提出以来，ETH 就一直是理论计算机科学中，用来证明某个问题到底有多难、算法下限在哪的最核心的基座之一。 插一句，其实还有SETH，强指数时间假设。如果ETH完蛋了，那SETH也完蛋了。ETH和SETH就是算法复杂度理论的“牛顿三定律”级别的基座。如果这些都是错误的，那很多技术护城河，就是纯废铁。 在学术界，有多少篇的论文都是建立在假设 ETH 为真的前提下展开推导的？ 答案是，很多很多。推特已经有人做了论文的总结。ETH彻底证明错误将失去任何价值的论文。ETH这个大前提被 AI 证伪了，意味着成千上万篇基于它的复杂度分析、衍生证明、理论模型，在逻辑的源头上瞬间失效，彻底失去意义。 你现在和ChatGPT、Claude聊，它可能会假惺惺地安慰你，说这是科学的必由之路，是人到机器火炬的传递。是的，我承认它们说的在某种意义上没错，但是这是科学本身的递进本质。我从来不否定对于整体人类和科学进步来说，ETH错误确实是一场伟大的纠错，但对于被大厦崩塌砸中的每一个活生生的个体来说，那些数十年的通宵不眠、熬干的心血、甚至为此放弃的无数个人生活，在一夜之间沦为废纸，其代价就是成为AI时代的炮灰。 在科学的漫长进程中，这种大厦一夜倾覆的个体悲剧曾无数次上演。当爱因斯坦证明绝对时空观错误时，无数研究了一辈子经典力学的物理学家在一夜之间失去了方向；当以太假设被证伪时，那些为之付出大半生心血的科学家也曾陷入同样的虚无与绝望。现在，我们仿佛就在那个节点上。

@dotey

OpenAI 宣布 AI 推翻“指数时间假设”（ETH）的同一天，Anthropic 在 GitHub 上放出一篇论文，得出同样的结论，署名作者只有一个：Claude。 论文说，核心算法是 10 月 16 日由一个内部研究版 Claude 找到的，用了 1400 万个输出 Token，没有人类输入。 OpenAI 说自己的模型也是 10 月 16 日找到的证明。

@realsinya

都说了王虹和那个搞笑的谁也没听过的卦谷定理就是一坨屎。菲尔兹奖颁给王虹，菲尔兹奖也是一坨屎。

@lidangzzz

我今天脑子炸了的另一个原因，是因为我就是k-SAT问题的直接受害者。 RSI Chip的终极目标，就是让Agent来agentically设计EDA，设计全世界一切所有的芯片，实现foundry signoff，而我只能用和cadence或者synopsys完全一样的CDCL来做SAT solver。 https://github.com/RSI-Labs/RSI-Chip LEC是当今VLSI design 里面最重要的一步，而商用SAT solver极有可能在这个问题被OpenAI推进一小步之后带来巨大优化。 至少如果你用kissat这种CDCL SAT solver来解决的话，worst case依然是exponential的，但是我完全相信至少在这个问题上可以推进一步。 我会再抽空研究研究，但是RSI Chip持续推进一定是停不下来的。

@xiaoxielaile

菲尔兹奖得主邓煜批评 AI 公司的双标： 训练模型时，恨不得把全人类的论文和知识都拿来喂 AI；轮到别人蒸馏自己的模型，却开始强调规则，连思维链都不愿公开。 吃人类知识红利时，讲技术进步；别人想学习你的模型时，就讲不能蒸馏。 AI 公司可以保护商业机密，但不能只在保护自己利益时才谈规则。 知识是全人类共同积累的，不能好处全拿，规则只给别人定。

@sleepy0x13

连菲尔兹奖得主都决定不再给学生的数学作业判对错了。 加州大学伯克利分校的数学教授 Richard Borcherds，1998 年菲尔兹奖得主，最近宣布改变作业评分方式，只要学生交了作业，就能拿到相应的分数，答案正确与否已经不重要了。 原因很简单，学生用 AI 做作业已经太普遍了，老师根本分辨不出哪些答案是学生自己写的。 Borcherds 说，继续按照正确率给分，只会鼓励更多学生使用 AI，反而惩罚那些老老实实自己做题的人。他现在主要依靠禁止使用电子设备的线下考试来检验学生的真实水平。 更有意思的是，他甚至开始怀疑自己还该不该建议年轻人投身数学研究。 他认为，如果 AI 继续以现在的速度进步，几年后人类数学家可能就没有什么事情能比 AI 做得更好了。他还专门去问 ChatGPT 应该怎么办，结果 ChatGPT 也不知道。 我觉得这件事挺有代表性的。AI 已经开始让大学最基础的评价机制失效了。 学生依然可以提交正确答案，拿到漂亮的成绩，但这些分数越来越难反映他们真正掌握了多少知识。 而最讽刺的是，连负责培养和评价人类智力的顶尖数学家，现在也不知道该怎么解决这个问题。

@lidangzzz

你的complexity第一节课的时候，老师就教过你，一大堆50年前的古典图问题、路径问题、各种flow和cut问题、一大堆set问题，全部都可以直接转化成3-SAT问题。 ETH就是保证整个这类问题的下限是exponential，如果ETH不能保证，整个计算机领域的一切这类问题，全都要重写， 至于重写到哪一步， 取决于The ETH is false之后到底能不能继续推动到polynomial的地步，一旦能的话，整个计算机理论就彻底消失了。 张雪峰说得对，只有土木才会永远不被替代。