理论计算机科学突破:William Hoza 证明 NL = UL
fortnow · x · 2026-11-21
William Hoza 在 ECCC 发布论文 TR26-323,证明 NL = UL——每个非确定性对数空间图灵机都可被无歧义对数空间图灵机模拟,这是计算复杂性理论的重要结果。
- 核心构造:一个显式权重分配生成器,仅用 O(log(wn)) 位空间,即可为任意简单分层有向图的每条边分配多项式有界的整数权重。
- 存在至少一个种子使权重函数 min-isolating:对所有可达的 s→t,最小权重路径唯一。
- 结合 Reinhardt 与 Allender 的 SICOMP 2000 工作,立即推出 NL = UL。
- 作者称构造与分析「 remarkably simple」;发布者戏称「结果很棒但挑了个糟糕的日子发布」。
「研究」频道最新
- 数学家解析黎曼猜想为何难:zeta 在 4/5 线可任意逼近零点 — AlexKontorovich · 2026-11-21
- 斯坦福 AI100 2026 报告发布:Scaling 时代与生成式 AI 成为主流 — stanfordnlp · 2026-11-21
- 新基准揭示前沿模型多智能体协作普遍不佳 — AlexGDimakis · 2026-11-21
- 黎曼猜想新结果引围观:论文引言文风戏剧化 — lishali88 · 2026-11-21
- 斯坦福 CS329Z 第九讲公开:Prompts vs Weights 的 Agent 优化全解 — stanfordnlp · 2026-11-21
- 斯坦福团队实证 EMA 权重平均:为何能降损失但略输给 LR 衰减 — stanfordnlp · 2026-11-21