OpenAI 发布 PDF 声称反驳指数时间假说:3SAT 或可近亚指数求解
rrwilliams · x · 2026-10-27
rrwilliams 分享了 OpenAI 的一份 PDF,其中声称对复杂性理论中的指数时间假说(ETH)给出反驳:核心结论是 n 变量的 3SAT 可在约 exp(n/(log n)^(1/2+o(1))) 时间内求解。若成立,这将动摇大量基于 ETH 的复杂性下界结果,但此类声明通常需经理论社区严格审查,真实性有待验证。
所属事件:OpenAI 声称反驳指数时间假说，3SAT 或可亚指数求解(2 条相关)→
「研究」频道最新
- 宾大 Kording 实验室为 2027 春季演讲系列公开征集学者提名 — KordingLab · 2026-10-27
- neuron-explorer 新增 MLX 支持，可在 Apple Silicon 上逐神经元探索 Qwen3.5-4B — arthurcolle · 2026-10-27
- OpenAI 宣布模型产出 Yang-Mills 存在性证明并完成 Lean 形式化 — exophades · 2026-10-27
- 3SAT 亚指数算法震动理论计算机科学，Bubeck 称 20 年最大意外 — danintheory · 2026-10-27
- gdb 宣布 AI 辅助拿下数学、复杂性理论与量子场论三项科学发现 — gdb · 2026-10-27
- 学术圈观察:AI 一边制造论文垃圾,一边清理人类遗留的学术垃圾 — _akpiper · 2026-10-27