Anthropic 的 Claude 推翻了指数时间假说,并给出了 Lean 证明(GitHub 仓库)

TLDR AI 新闻

摘要

Anthropic 发布了 formal-math GitHub 仓库,收录了经机器验证的 Lean 4 形式化证明。其中,Claude 生成的证明在 Lean 中形式化了一种计算 k-CNF 公式满足赋值数量的算法,从而推翻了指数时间假设(ETH);仓库还包含黎曼 ζ 函数零点以及 3SUM/APSP 等相关结果的形式化证明。

Anthropic 表示,其内部研究用 Claude 模型在没有任何人类输入的情况下,发现了一种确定性算法,能在 2^O(n log log n/√log n) 时间内计算 3-SAT 公式的满足赋值数量,这将使 3-SAT 可在亚指数时间内求解,并推翻指数时间假设(ETH)。该代码仓库存放了论文以及由 AI 模型编写的 Lean 4 形式化证明,后者约需 8 分钟即可完成构建。不过,Anthropic 指出,并没有机器检查来确认 Lean 中的命题是否与论文一致,而且这一结果并不涉及实际 SAT 求解的性能。该成果发布于 OpenAI 自己的 ETH 反驳成果发布数小时后。
查看原文
查看缓存全文

缓存时间: 2026/10/29 01:24

anthropics/formal-math 来源:https://github.com/anthropics/formal-math # formal-math Anthropic 发布的经机器检查的 Lean 4 形式化成果。每个子目录都是一个独立的 Lake 项目,具有各自固定的工具链版本、README 和构建说明;请在子目录内进行构建。项目遵循 Palomar (https://palomar-registry.org/) 提交模板的布局(项目根目录下包含 Challenge.lean / Solution.lean / comparator.json / formalization.yaml),并以该子目录作为选定项目提交至 Palomar;Palomar 读取的许可证文件是本仓库根目录下的 LICENSE。 | 项目 | 命题 | Lean / Mathlib | |—|—|—| | zeta23/ | 黎曼 ζ 函数超过三分之二的零点是单零点且位于临界线上(Alpöge–Furman,arXiv:2608.13637) | leanprover/lean4:v4.33.0-rc2 / Mathlib v4.33.0-rc2 | | 3sum-apsp/ | 字长 RAM 程序可在 O(n^1.9992) 步内求解 3SUM,并在 O(n^2.99942) 步内求解 (min,+) 乘积和 APSP,所处理整数的大小为多项式量级;还逐项涵盖 Exact Triangle 和 Zero-Weight k-Clique 的界,以及论文中的其他结果(Alman–Vassilevska Williams,arXiv:2610.06783) | leanprover/lean4:v4.33.1 / Mathlib v4.33.1 | | eth/ | 存在一台确定性图灵机,对于每个具有 m ≥ 2 个子句、n ≥ 4 个变量且每个变量均有出现的 k-CNF,均可在 2^O(min{k^2 n log log n/√log n, km/√log m}) 步内计算其满足赋值的数量,从而推翻指数时间假设(Claude,文件夹内的论文) | leanprover/lean4:v4.33.1 / Mathlib v4.33.1 | ## CI 拉取请求和向 main 的推送会对文件发生更改的每个项目文件夹运行 .github/workflows/lean-projects.yml,且仅对这些文件夹运行;仅涉及 CI 配置或文档(.github/、本 README 等)的更改不会验证任何内容,所有项目的完整运行需从 Actions 选项卡手动启动(workflow_dispatch,projects = all)。如果设置了仓库或组织变量 LEAN_CI_RUNNER,verify 作业将在该变量指定的运行器标签上运行(例如 ubuntu-latest-16-cores 这样的 GitHub 大型运行器),否则在 ubuntu-latest 上运行。拉取请求的运行会复用该项目在相同工具链和清单下的上一次 Lake 构建(仅重新构建发生更改的模块);合并到 main 和手动运行则从头构建。项目通过验证需要满足以下条件:在其固定版本的工具链上成功执行 lake build,且受信任的比较器命题文件(Challenge.lean、Challenge/.lean)之外不存在 sorry;同时,Palomar 注册表 (https://github.com/PalomarRegistry) 的验收检查——使用与工具链匹配的 lean4export、独立的 nanoda 内核和 landrun 沙箱,并采用注册表固定的工具版本运行 leanprover/comparator (https://github.com/leanprover/comparator)——对项目声明的每个比较器配置都输出 Your solution is okay!(.github/scripts/comparator-check.sh;在本地使用 cd && bash ../.github/scripts/comparator-check.sh 运行)。添加项目的方法:创建一个顶层目录,其中包含 lakefile.toml(或 lakefile.lean)、lean-toolchain、lake-manifest.json、一个仅依赖 Mathlib 且陈述主要定理的 Challenge 模块、一个基于库证明这些定理的 Solution 模块,以及至少一个比较器配置(与 lakefile 同级的 comparator.json,或 comparator/config*.json);在上表中添加一行。 ## 许可证 Apache-2.0——参见 LICENSE。各个项目可能附带额外的 NOTICE 文件。

相似文章

指数时间假设已被证伪 [pdf]

Lobsters Hottest

OpenAI 发布了一个包含 721 篇数学手稿的仓库,这些手稿由一个未公开名称的内部模型生成,其中包括一项声称推翻指数时间假设(ETH)的成果。其中约 42% 的结果已在 Lean 中完成形式化验证,并附有精简的推理轨迹。

理解指数时间假设,以及 OpenAI 宣称其为假的说法

Reddit r/singularity

OpenAI 宣称发布了一篇证明指数时间假设(ETH)为假的论文,主定理已通过 Lean 验证,并由 Impagliazzo、Paturi 和 Williams 领导的独立工作组进行审查;文章通俗解释了 3-SAT、NP 完全性以及 ETH 被证伪可能带来的深远影响。

OpenAI 和 Anthropic 均声称能在 2^o(n) 时间内求解 3-SAT,推翻指数时间假说——一部用 Claude 制作的 43 分钟讲解视频

Reddit r/singularity

OpenAI 和 Anthropic 均声称,其内部 AI 模型各自独立地通过在 2^o(n) 时间内求解 3-SAT,推翻了指数时间假设。这一结果附有 Lean 证明证书,但尚未经人类专家审查。这篇文章是一篇阅读时长为 43 分钟的解说,介绍了这两个证明、它们极其庞大的运行时间,以及该如何看待此类声明。