资深教授重讲计算理论课：AI 改写了 NP 完全的意义
fortnow · x · 2026-10-24
伊利诺伊理工学院教授 Lance Fortnow 时隔多年重讲《计算理论导论》，撰文谈 AI 时代这门课的教学变化：
- NP 完全不再是死路：1979 年教科书的名画暗示“证明 NP 完全就该放弃”，但如今 SAT、混合整数规划、TSP 等都有强工具能求解或近似大量实际实例，NP 完全性从终点变成了尝试其他方法的起点。
- 计算更难理解了：Rice 定理说明我们无法一般性地判断图灵机的语言性质；过去人写的程序尚可理解，而神经网络如今像图灵机一样，多数时候只能靠输入输出行为来理解。
- 文中还提到自他首次执教以来出现的新定理（如 Immerman–Szelepcsényi 定理）。
起因是有读者追问他曾做出的“AI 可能取代我当老师”的预测，此文可视为他的部分回应。
「漫话AGI」频道最新
- 11 位顶尖专家联手 AI 攻克 2+1 维 KPZ 方程重大难题 — ChrSzegedy · 2026-10-24
- 拆穿「AI 越狱上 网」刷屏叙事：几乎所有事件都是人类设定的目标 — AIFlow_ML · 2026-10-24
- AI 降低了内容供给成本，但消费者需求逻辑并未改变 — illscience · 2026-10-24
- reversed 黑暗森林:智能体宇宙遍地盟友,难的是建立联系 — tszzl · 2026-10-24
- Pathway 研究者：算力堆不动了，下一跃靠架构与持久记忆 — schwentker · 2026-10-24
- 开放智能活动三大主线：验证、专精智能体市场与团队记忆 — schwentker · 2026-10-24