「指数时间假设不成立」？理论计算机圈惊传重磅断言
davidad · x · 2026-10-27
Andrew Curran 在 X 上宣称指数时间假设(ETH)不成立并附论文链接，davidad 转发扩散。ETH 断言 3-SAT 等问题不存在亚指数时间算法，是计算复杂性理论与大量下界证明的基石；若被推翻，将动摇许多 hardness 证明的前提，属理论计算机科学的重大消息(结论有待社区验证)。
所属事件:OpenAI 64 页论文宣称推翻指数时间假说，并附 Lean 形式化(7 条相关)→
「研究」频道最新
- 约翰霍普金斯等推 OpenTac：可定制可量产的机器人 3D 触觉皮肤开源生态 — _krishna_murthy · 2026-10-27
- NeurIPS 论文：任务越难 LLM 内部表征越稀疏，还可据此优化 ICL — zhaoran_wang · 2026-10-27
- Neuron Explorer 工具 3D 可视化 Transformer 逐层神经元激活 — arthurcolle · 2026-10-27
- Bengio 等人新论文:用算法信息论给「组合性」下普适度量 — patrickmineault · 2026-10-27
- 对模型而言，「经验教训」类论文可能比 2500 引用的图谱论文更有用 — owl_posting · 2026-10-27
- AI 产出指数时间假设的反例，P=NP 赔率一夜收紧 — esrtweet · 2026-10-27