通过机器学习达到人类水平的表现 *并未* 被复杂性理论证明为不可能 [D]

Van Rooij、Guest、Adolfi、Kolokolova 和 Rich 在2024年于 *Computational Brain & Behavior* 上[声称已证明通过机器学习实现AGI是不可能的](https://link.springer.com/article/10.1007/s42113-024-00217-5)。其基本思路是试图将一个已知的NP难问题简化为从数据中学习人类级别分类器的问题。这一被称为“Ingenia定理”的所谓结果在互联网上引起了一些关注，包括在这里。我证明该证明存在不可修复缺陷的论文现已[同样发表在CBB上](https://link.springer.com/article/10.1007/s42113-026-00284-w)（无付费墙预印本[在此](https://arxiv.org/abs/2411.06498)）。基本问题在于“人类级别分类器”在数学上未定义，而作者解决这个问题的方式是……从未定义它。他们在介绍问题时有一个对应于“人类情境-行为元组分布”的构造，但在进行正式证明时，这个构造被替换成了“对于所有多项式时间可采样的分布”。这意味着，如果对人类情境-行为元组进行查找替换为ImageNet输入/标签，这篇论文也证明了学习分类ImageNet是不可行的。关于从Penrose到Chomsky类似尝试的博客讨论[在此](https://mikeguerzhoy.substack.com/p/barriers-to-complexity-theoretic)。