OpenAI推翻指数时间假设 原提出者称震惊

据《纽约时报》报道，OpenAI宣布其AI系统推翻了理论计算机科学的基石之一——指数时间假设（ETH），结论已在形式化证明语言Lean中通过验证。该假设的共同提出者、加州大学圣地亚哥分校教授拉塞尔·因帕利亚佐（Russell Impagliazzo）在接受采访时称这一结果「令人震惊」。

指数时间假设由因帕利亚佐与帕图里（Ramamohan Paturi）等人在上世纪90年代末提出，核心主张是：不存在能在亚指数时间内解决所有3-SAT可满足性问题的算法。近30年来，从图论到数据库再到计算生物学，已有数百篇论文以它为前提，推导各类问题的计算难度下界。

OpenAI公布的证明显示，其内部模型为一类布尔公式构造了确定性算法，运行时间降至亚指数级（约2^O(n/√log n)），不仅能判断问题是否有解，还能精确统计满足条件的解的数量。若结论最终成立，ETH即被证伪，不过学界审查仍在进行中。

与以往直接发布论文不同，OpenAI这次邀请麻省理工学院计算机科学家瑞安·威廉姆斯（Ryan Williams）牵头组织外部验证团队，成员恰恰包括ETH的原始提出者。三人未签保密协议，也未收取报酬。因帕利亚佐透露，OpenAI发来的第一版证明「完全无法阅读」，团队随后重制了一份可读版本再对外公开。

潜在影响深远：这类加速有朝一日可能用于芯片设计等实际领域，也可能动摇依赖计算困难性的加密体系。推翻ETH也被视为朝著名的千禧年大奖难题「P与NP」迈出的重要一步。

OpenAI已在公开代码仓库发布自然语言证明文稿与Lean证明，并承诺公开全部原始数据、资助一场学术会议。评审工作组计划年底前举行线上评审、2027年举办线下会议。学界在震惊之余也在反思：当AI能批量产出数学成果，人类研究者的角色正被重新定义。

编译自 OpenAI 官方博客及《纽约时报》报道，原标题："Working with academic communities to build scientific understanding"