若 ETH 为假 NP 仍是指数时间:归约的多项式因子挡住了
robleclerc · x · 2026-10-28
LDanilek 复盘一个复杂度直觉的修正:起初以为 ETH(指数时间假设)为假意味着所有 NP 问题都有亚指数算法——把任意 NP 问题归约到 NP 完全的 3-SAT 再亚指数求解即可。但此路不通:归约会引入多项式因子,若某 NP 问题归约到立方规模的 3-SAT,已知最好解法仍是指数时间。作者称暂时松了口气,但怀疑在这个「屏障被突破」之后还会有新的进展。
「研究」频道最新
- UCLA 清华论文：让编程智能体用代码作画，跨接口保持一致场景表征 — ucla-cmllab · 2026-10-28
- OpenAI 与 Anthropic 疑似推翻 ETH 后,衍生出亚指数级哈密顿圈算法 — xennygrimmato_ · 2026-10-28
- 亚指数时间精确计算哈密顿圈数:依赖 ETH 反驳的新算法结果 — xennygrimmato_ · 2026-10-28
- 作者自曝:线程由 Claude 和 ChatGPT 撰写,文章出自 Nigam Shah — jonc101x · 2026-10-28
- 信任医疗 Agent 执行真实临床任务还缺什么 — jonc101x · 2026-10-28
- 医疗 AI 最弱环节恰是临床决策支持与行政工作流 — jonc101x · 2026-10-28