Ladner定理视角下的NP中间问题猜想被打破：NPI未必只有次指数解
yacineMTB · x · 2026-10-27
Peter Schmidtnelson（ptrschmdtnlsn）就 NP 中间问题发推：由 Ladner 定理，若 P≠NP 则 NP 中间问题（NPI）非空。他一直以为最终结局是 NPI 中的问题会存在次指数级算法（甚至可能落入 BQP），而 NP 完全问题则没有——但最新进展表明并非如此。这是对某项复杂度理论结果的学术评论，属于理论计算科学讨论。
「研究」频道最新
- 学者质疑 DoM 引导方法：定位方法选对层不代表两者都正确 — johnhewtt · 2026-10-27
- 可解释性争论:定位+DoM 有效不代表定位方法正确 — johnhewtt · 2026-10-27
- 马普所「外星重组」论文:让 AI 搜寻人类认知盲区外的概念组合 — profjamesevans · 2026-10-27
- 播客:James Evans 谈推理模型模拟「思想社会」与自复制程序实验 — profjamesevans · 2026-10-27
- 单核 24GB/s：新开源 AVX-512 哈希函数 PikasekoHash-256 发布 — ssh4net · 2026-10-27
- ETH 反驳共享库现 Anthropic 文件夹，疑藏同一结果新证明 — NoahSD · 2026-10-27