「指数时间假设」不成立！OpenAI和A社同日出大结果了

鱼羊 发自 凹非寺
量子位 | 公众号 QbitAI

计算复杂性理论要变天了。

还是AI。并且这一次，是OpenAI和Anthropic同时出手。

刚刚，两家前后脚宣布，在10月16日，他们分别用自己的「内部模型」，把指数时间假设（ETH）推翻了。

何意味啊？这么说吧。。。ETH与著名的「P≠NP」密切相关。

在此之前，学界是普遍认为ETH成立的，非常非常多论文都是以此为前提，推导出了一系列图论、计算生物学、数据库、计算几何等等等等领域的计算复杂度结论……

连OpenAI自己在公布这项成果时，都说ETH不成立这事儿，咱也没想到啊！

目前，OA两家都已经给出了形式化证明（Lean）结果。

OpenAI这边还把指数时间假设最初的提出者Russell Impagliazzo和Ramamohan Paturi拉上了：由Russell Impagliazzo、Ramamohan Paturi，以及麻省理工数学家Ryan Williams组成的小组将负责验证并推动后续研究。

OpenAI已应数学家要求，公开这项成果的所有原始数据。

ETH被推翻

所谓「指数时间假设」，是计算复杂性理论中的一个计算难度假设，它假设3-SAT问题不能在次指数时间内解决。

3-SAT是一道通用的逻辑判断题：

有n个只能取真或假的变量，每条约束含至多三个文字项。问题是，能否找到一组赋值，让所有约束同时成立？

例如：

暴力尝试有2ⁿ种赋值。ETH主张，在时间复杂度上，即使用最优算法，最坏情况仍有一个无法突破的正指数增长率。

即数学表述是，3-SAT不存在2^o(n)时间算法。

为什么这个问题很重要呢？

实际上，3-SAT就是经典的NP完全问题。如果指数时间假设（ETH）成立，则意味着P≠NP，并且许多已知算法具有最优或接近最优的时间复杂度。

△AI生成

来看OpenAI和Anthropic如何证明ETH其实是不成立的。

OpenAI：次指数时间计数，且只需多项式空间

OpenAI的内部模型找到了一种算法，能用次指数时间精确算出逻辑公式有多少个解，同时只需多项式空间。

这样一来，原来认为这类问题必然需要指数时间的ETH就不成立了。

论文中，一般情形的时间界为：

其中n是变量数，m是约束数。O_k表示隐藏常数可以依赖k。n增长时，k固定，例如始终取3。

内存使用为 (n+m)^Ok(1)。也就是输入变大时，所需存储只按某个固定次幂增长，不必同时存下指数数量的中间结果。

若公式较稀疏，约束数满足m≤Dn，且D固定，论文把时间界进一步改进为：

Lean覆盖的界略弱，但同样足以反驳ETH。范围说明给出的形式化时间界是：

其中L是规范编码的输入比特长度。

Anthropic：固定k的精确计数可以在次指数时间完成

和OpenAI一样，Anthropic的论文同样证明了，固定k的精确计数可以在次指数时间完成。

精确计数所需的时间为：

min的意思是，两个界中取更小的那个。一个看变量数n，一个看约束数m。这里隐藏的绝对常数不依赖k。

当k固定，一般界同样有2^{O(nlog⁡log⁡n/√log⁡n)} 的形式。若m与n成正比，还可得到2^{O(n/√log⁡n)} 的稀疏情形界。

这些主时间界与OpenAI论文在对应固定参数下的形式接近。

Anthropic还在论文中强调，推翻ETH的核心算法完全由内部Claude模型独立发现。不过人类研究员参与了改进算法呈现方式的部分。

目前，两家的结论都尚待同行评审。

若结论最终被验证成立，就意味着，大量依赖ETH的计算困难型判断需要重审。

三位被OpenAI写进公告的数学家们就发文表明了态度：

我们的参与不应被视为对该主张的认可。

如此重要的结果需要经过谨慎、独立的审查，并且其他人可以对其进行重构、质疑和拓展。

数学家们一方面正在组织对这一重要结果的审查，另一方面也希望大家“思考我们的社区应如何更广泛地应对AI带来的突破性进展”。

我们预期AI会产生更多挑战既有假设、或开辟全新研究方向的结果。

嗯，科学范式的变化已经席卷数学界，下一个又会是……