Aaron Roth:用最坏情形复杂度论证 AI 不可能是个坏论据

Aaroth · x · 2026-09-14

宾大理论计算机科学家 Aaron Roth 发推批评一种流行论调：用计算复杂度理论论证「真正的 AI」不可能被造出来。他认为这种论证令人恼火，因为它无视眼前的事实——最坏情形复杂度分析在机器学习历史上一直是糟糕的指南。后续推文中他举例：连最简单的机器学习问题(最小化分类误差的线性分类器)都是 NP 难甚至难以近似的,但现实中这类问题几乎都被解决了,说明最坏情形模型虽然优雅,却无法预测自然问题上的实际可行性。