3-SAT 亚指数时间解引热议，计算机科学家详解「指数时间」两种含义
aran_nayebi · x · 2026-10-31
理论计算机科学家 TCzajka 针对新的 3-SAT 亚指数时间结果，科普了复杂度理论中「指数时间」的歧义。
- 两种「指数时间」：类 E（2^O(n)，即 O(c^n)）与更宽的 EXPTIME（O(2^(n^k))，本质是多项式的指数）；后者是命名失误但因对多项式归约封闭而成为惯例，所有 NP 问题都在 EXPTIME 中。
- 亚指数时间同样有两种定义：2^o(n)（对每个 ε>0 为 O(2^(εn))）等，不同定义下「亚指数算法」的结论强度完全不同。
- 帖子旨在澄清媒体报道新结果时容易产生的混淆。
「研究」频道最新
- 在 RNN 单元加入 Tversky 相似度分支，一半深度追平全深度并提速 2 倍 — stanfordnlp · 2026-10-31
- AI 将 NP 问题电路下界从 3.1n 推至 3.5n，UCLA 发起人机协作冲 P≠NP — soumitrashukla9 · 2026-10-31
- Qwenputer：把完整 RISC-V CPU 塞进 Qwen3.5-4B 权重里 — armand_ruiz · 2026-10-31
- AI 时代工作意义何在？跨国调查：81% 的人对工作满意 — soumitrashukla9 · 2026-10-31
- 论文：基准测试难度分布失真，榜单结论需谨慎解读 — Miserable-Dare5090 · 2026-10-31
- AISTATS 2027 workshop 提案截止延至 11 月 6 日 — qberthet · 2026-10-31