计算复杂度奠基人、图灵奖得主 Richard Stearns 逝世,享年 90 岁
fortnow · x · 2026-09-05
计算复杂度领域先驱 Richard Stearns 于 2026 年 8 月 29 日逝世,享年 90 岁。他与 Juris Hartmanis 1965 年的论文《On the computational complexity of algorithms》首次定义了 DTIME(T(n)) 等复杂度类,并为整个领域命名,两人因此获得 1993 年图灵奖。
Fortnow 的博客还介绍了 Stearns 一篇较少人知的杰作:他与 F. C. Hennie 合作的论文,给出了至今仍是最紧的确定性时间层次分离。文中还回顾了相关的自动机状态转换问题:NFA→DFA 的 2^n 上界、CFG→PDA 的线性上界,而「CFG 描述正则语言的最小 DFA 大小」这类函数则不可计算,其难度归约自 HALT/INF。
Stearns 曾在博客 50 周年时主动寄来 1963 年他与 Hartmanis 在黑板前的合影。
「研究」频道最新
- MultiMDM:让掩码扩散语言模型「先打草稿」实现少步生成 — QuanquanGu · 2026-09-05
- Google DeepMind 推出免费在线书《How To Scale Your Model》讲透 TPU 上 LLM 扩展 — goyal__pramod · 2026-09-05
- 开发者优化 MoE 内核:BF16 提速 1.2 倍,MXFP8 提速 1.6 倍 — retr0jirachi · 2026-09-05
- 数学家 Kevin Buzzard 独立验证 Anthropic 的 FLT Lean 证明:确实成立 — AlexKontorovich · 2026-09-05
- Prime Intellect 用 NIXL 把万亿参数 RL 权重同步从 86 秒压到 4 秒 — samsja19 · 2026-09-05
- Karpathy「先过拟合再正则化」原则在大规模后训练时代依然成立 — rdesh26 · 2026-09-05