Ryan Williams 界定新 3SAT 算法边界：亚指数但非多项式
AIFlow_ML · x · 2026-10-27
针对复杂度理论新发现的讨论，AIFlowML 引述 Ryan Williams 的原话给出精确边界：新结果给出的 3SAT 算法在 n 变量上约需 exp(n/(log n)^{1/2+o(1)}) 时间，渐近低于所有 2^(cn) 形式的算法，但并非多项式时间；论文本身也明确声明，这并不意味着所有 NP 问题都可亚指数求解。这条澄清为「ETH 被推翻」的宣称划定了实际范围。
所属事件:OpenAI 宣布 AI 连获数学、复杂性理论与物理三项重大发现(63 条相关)→
「研究」频道最新
- 英矽智能生成式 AI 设计的抗癌药 ISM6331 报 40% 客观缓解率 — rand_longevity · 2026-10-27
- 强化学习不只奖励深思，还会催生并行协作的agent集群 — rosstaylor90 · 2026-10-27
- 音频倒放频谱幅度不变:一文讲透时频分辨率权衡 — techNmak · 2026-10-27
- 学者质疑 DoM 引导方法：定位方法选对层不代表两者都正确 — johnhewtt · 2026-10-27
- 可解释性争论:定位+DoM 有效不代表定位方法正确 — johnhewtt · 2026-10-27
- 马普所「外星重组」论文:让 AI 搜寻人类认知盲区外的概念组合 — profjamesevans · 2026-10-27