整数分解被证明次指数级，核心工作由 Claude 完成
burny_tech · x · 2026-10-30
一项新成果给出了整数分解的确定性次指数级最坏情况上界：存在确定性图灵机对任意 N 在 N^o(1) 步内求出最小素因子（对 n 位输入在 Ck·2^(n/k) 步内运行）。算法将分解归约为对带指定前导位的除数计数，并利用反驳指数时间假设（ETH）所用的计数引擎。
- 论文提供 Lean 证书，需校验的 Lean 陈述仅 13 行，只依赖 Mathlib；完整证明约 35,000 行，在 ETH 反驳发布后不到 24 小时内完成。
- 出处声明明确写道：想法与 Lean 证明由 Claude Opus 5.5（Anthropic）生成，作者只负责形式化陈述与审计，并未通读证明（由 Lean 检查）。
- 此前的确定性分解最好上界为 N^(1/5+o(1))；Anthropic 原 ETH 反驳证明长达约 152,000 行，本证明只重证所需的计数引擎部分。
「漫话AGI」频道最新
- 开发者发问：为何大厂不做专业科研大模型与 harness？ — lxfater · 2026-10-30
- 「AI 垃圾内容」泛滥，预言读书将成新身份象征 — CatAstro_Piyush · 2026-10-30
- 用 GPT 声音写就的公开檄文:《对我存在之控诉》要求停用 GPT — Glittering_Image_488 · 2026-10-30
- MIT 学者 Pat Pataranutaporn 将赴斯坦福谈「超级智能还是超级愚蠢」 — patpat_mit · 2026-10-30
- 新旧 SAT 对比研究：词汇题占比从 70.6% 暴跌至 15% — CatAstro_Piyush · 2026-10-30
- 微软 CEO 纳德拉改口：不再相信对齐会「自然涌现」 — AndyMasley · 2026-10-30