O(n) 边图中哈密顿环数可亚指数精确计算,Lean 已形式化验证
xennygrimmato_ · x · 2026-10-28
作者声称,假设近期对指数时间假设(ETH)的反驳成立,O(n) 条边的 n 顶点图中哈密顿环的数量可以确定性地在亚指数时间内精确计算——此前所有该问题算法都是指数级的。要点:- 论文给出更精细的速率 2^{O(n/√(log n))},与新的 SAT 算法匹配;- 亚指数界已在 Lean 中形式化验证,基于并重建了 OpenAI(openai/math)与 Anthropic(anthropics/formal-math)于 10 月 26 日发布的 Lean 证明;- 工作仍待人类专家评审,结果仅限稀疏图且是条件性的;- 代码与论文已开源在 GitHub(eth-hamiltonicity 仓库)。
所属事件:研究者基于 ETH 反驳推出哈密顿圈亚指数算法(3 条相关)→
「研究」频道最新
- Rachel Thomas 引经典论文：论证「不造技术」也是一种价值 — math_rachel · 2026-10-28
- Meta 开源级翻译系统 Omnilingual MT 覆盖 1600 种语言 — kalyan_kpl · 2026-10-28
- 用 logprobs 把 LLM 从硬分类器升级为可调阈值的软分类器 — JnBrymn · 2026-10-28
- cryoET 数据门户上线 xLPP 交叉激光相位板三组对比数据集 — ZhongingAlong · 2026-10-28
- 无视觉盲操保定球：机械手连续 225 次旋转不掉球 — Scobleizer · 2026-10-28
- AgiBot等发布Rollback:用世界模型回溯决策点改进机器人策略 — agibot-world · 2026-10-28