「指数时间假设」不成立！OpenAI和A社同日出大结果了
刚刚，两家前后脚宣布，在10月16日，他们分别用自己的「内部模型」， 把 指数时间假设 （ETH） 推翻了 。
在此之前，学界是普遍认为ETH成立的，非常非常多论文都是以此为前提，推导出了一系列图论、计算生物学、数据库、计算几何等等等等领域的计算复杂度结论……
OpenAI这边还把 指数时间假设最初的提出者 Russell Impagliazzo和Ramamohan Paturi拉上了：由Russell Impagliazzo、Ramamohan Paturi，以及麻省理工数学家Ryan Williams组成的小组将负责验证并推动后续研究。
ETH被推翻
所谓「指数时间假设」，是计算复杂性理论中的一个计算难度假设，它假设3-SAT问题不能在次指数时间内解决。
有n个只能取真或假的变量，每条约束含至多三个文字项。问题是，能否找到一组赋值，让所有约束同时成立？
暴力尝试有2 n 种赋值。ETH主张，在时间复杂度上，即使用最优算法，最坏情况仍有一个无法突破的正指数增长率。
实际上，3-SAT就是经典的 NP完全问题 。如果指数时间假设 （ETH） 成立，则意味着P≠NP，并且许多已知算法具有最优或接近最优的时间复杂度。
OpenAI：次指数时间计数，且只需多项式空间
OpenAI的内部模型找到了一种算法，能用次指数时间精确算出逻辑公式有多少个解，同时只需多项式空间。
其中n是变量数，m是约束数。O k 表示隐藏常数可以依赖k。n增长时，k固定，例如始终取3。
内存使用为 (n+m) Ok (1) 。也就是输入变大时，所需存储只按某个固定次幂增长，不必同时存下指数数量的中间结果。
Anthropic：固定k的精确计数可以在次指数时间完成
和OpenAI一样，Anthropic的论文同样证明了，固定k的精确计数可以在次指数时间完成。
min的意思是，两个界中取更小的那个。一个看变量数n，一个看约束数m。这里隐藏的绝对常数不依赖k。
当k固定，一般界同样有2 O (nloglogn/√logn) 的形式。若m与n成正比，还可得到2 O (n/√logn) 的稀疏情形界。
Anthropic还在论文中强调，推翻ETH的核心算法完全由内部Claude模型独立发现。不过人类研究员参与了改进算法呈现方式的部分。
我们的参与不应被视为对该主张的认可 。 如此重要的结果需要经过谨慎、独立的审查，并且其他人可以对其进行重构、质疑和拓展。
数学家们一方面正在组织对这一重要结果的审查，另一方面也希望大家“思考我们的社区应如何更广泛地应对AI带来的突破性进展”。
我们预期AI会产生更多挑战既有假设、或开辟全新研究方向的结果。