指数时间假设还站得住吗:从平凡 1.913^n 算法谈起
minilek · x · 2026-10-28
minilek 向复杂度圈专家提问:除了「聪明人还没找到更快算法」之外,历史上有什么理由相信 ETH(指数时间假设)应该成立?他指出「不比暴力搜索好」其实早已不成立——一系列论文把 SAT 的指数底数 c<2 越压越小,事后看足以让人对 ETH 感到悲观。他还给出直观演示:取第一个子句递归尝试其 7 种不立即矛盾的真值赋值、跳过第 8 种,由 T(n)=7·T(n-3) 即得 O(1.913^n)——说明得到某个 c<2 几乎是平凡的,挑战在于把 c 压向多低。
「研究」频道最新
- mHC 残差流疑随深度收敛,DeepSeek v4 实验者推荐 iHC 引发讨论 — teortaxesTex · 2026-10-28
- Qwenputer：把 32 位 RISC-V CPU 编进 Qwen3.5 权重，Gated DeltaNet 当内存 — LatentSpacer · 2026-10-28
- Meta 首个 Loop Scaling Laws：循环叠加稀疏带来约 2 倍参数效率 — yacinelearning · 2026-10-28
- Anthropic 实验:77% 专家复述 Agent 论点,仅 15% 认为归功于它 — paulnovosad · 2026-10-28
- 通用接触规划+跟踪+神经映射，人形机器人移动登上新台阶 — ChongZzZhang · 2026-10-28
- 计量经济学顶刊论文现身说法:Andrews 与 Mikusheva 谈 AI 写作冲击 — paulnovosad · 2026-10-28