OpenAI 与 Anthropic 疑似推翻 ETH 后,衍生出亚指数级哈密顿圈算法
xennygrimmato_ · x · 2026-10-28
一位研究者基于 OpenAI(openai/math)与 Anthropic(anthropics/formal-math)于 10 月 26 日发布的 ETH(指数时间假设)反驳证明,推导出新的算法结果,并开源了完整论文与代码(GitHub 仓库 eth-hamiltonicity)。要点:
- 核心结论:若两家的 ETH 反驳成立,则在 |E|=O(n) 的稀疏图上,可以确定性地以亚指数时间精确计算哈密顿圈的数量;此前通用稀疏图的最佳算法仍是指数级。
- 更精细的速率:配套论文给出 2^{O(n/√log n)} 的上界,与新的 SAT 算法速率吻合。
- 形式化验证:亚指数界已在 Lean 中机器验证,证明构建在两家实验室的 Lean 证明之上(作者重建了两家的证明)。
- 注意:所有结果均为渐近性且条件依赖于尚未通过人类专家评审的 ETH 反驳。
所属事件:研究者基于 ETH 反驳推出哈密顿圈亚指数算法(3 条相关)→
「研究」频道最新
- 逐个神经元扫 Qwen3-8B,用 Haiku 给怪异度打分 — Sauers_ · 2026-10-28
- 研究者跟进 OpenAI/Anthropic 的 ETH 反驳声明，发布 Lean 机器校验的哈密顿回路结果 — xennygrimmato_ · 2026-10-28
- DiscoTrace 获 EMNLP 最佳论文:LLM 答题策略缺乏人类式的社区多样性 — TuhinChakr · 2026-10-28
- arXiv 新论文提出世界模型表征的三问框架：可达性、准入与指派 — SoloGen · 2026-10-28
- OpenAI 发布内部前沿模型数学成果，Terence Tao 长文回应消化之道 — krisspy39 · 2026-10-28
- Divergence Labs 联手 Anthropic 用 Claude 发现食物过敏抗体疗法 — anshulkundaje · 2026-10-28