Ryan Williams 科普：ETH 为假对复杂性理论意味着什么
rrwilliams · x · 2026-10-27
面对非专业读者的提问，Ryan Williams 用通俗语言解释指数时间假设（ETH）：ETH 主张 3SAT 无法在 1.000...01^n（哪怕略优于 2^n 暴力搜索）的时间内求解。而相关声明声称 ETH 为假，给出了 3SAT 的「亚指数」时间算法——这将是对暴力搜索出人意料的巨大加速。
所属事件:OpenAI 宣布 AI 连获数学、复杂性理论与物理三项重大发现(63 条相关)→
「研究」频道最新
- 马普所「外星重组」论文:让 AI 搜寻人类认知盲区外的概念组合 — profjamesevans · 2026-10-27
- 播客:James Evans 谈推理模型模拟「思想社会」与自复制程序实验 — profjamesevans · 2026-10-27
- 单核 24GB/s：新开源 AVX-512 哈希函数 PikasekoHash-256 发布 — ssh4net · 2026-10-27
- ETH 反驳共享库现 Anthropic 文件夹，疑藏同一结果新证明 — NoahSD · 2026-10-27
- AI 推翻指数时间假说?附图对比声称的次指数算法与 2ⁿ 增长曲线 — robleclerc · 2026-10-27
- OpenAI 疑似进展触及 3-SAT，指数级难题被指遭挑战 — micoolcho · 2026-10-27