Ryan Williams 解析 OpenAI 破 ETH 算法:属 split and list 类
rrwilliams · x · 2026-10-30
在关于 OpenAI 疑似违反指数时间假设(ETH)求解器的讨论中,理论计算机科学家 Ryan Williams 认为,该算法属于一类「split and list」方法:把变量拆成小块,枚举块内所有赋值,再用 P 问题把各块结果「拼接」起来,从而将 NP 问题归约为指数规模的 P 问题实例。这是对这一突破性结果所属算法框架的一个定性回答。
所属事件:理论学家解析OpenAI破ETH求解器：属split and list算法(2 条相关)→
「研究」频道最新
- Meta 论文:RL 后训练提升首次成功率,却收窄解题覆盖面 — rohanpaul_ai · 2026-10-30
- AI 加持生信工具再提速:bowtie2 提升 3 倍、bwa-mem3 提升 20-30% — jmschreiber91 · 2026-10-30
- Jason Furman 谈 AI 与经济学研究：AI 该在前沿和复现中发挥大作用 — Afinetheorem · 2026-10-30
- ScreenBench:湿实验室数据藏错,AI agent 最高仅得 0.49 分 — danielmckinn0n · 2026-10-30
- Mastra Observational Memory 登顶 BEAM 长期记忆基准 100K/1M 榜首 — darian314 · 2026-10-30
- Rooke 称69个Lean验证SAT定理、比CaDiCaL快22.92倍，但P vs NP仍开放 — TinfoilTricorn · 2026-10-30