OpenAI 最近在 GitHub 的 openai/math 仓库中又公开了一项由内部 AI 模型完成的数学研究成果：《The Exponential Time Hypothesis Is False》，翻译过来就是“指数时间假设是错误的”。

如果这个结果最终得到学术界认可，绝对是理论计算机科学领域的一项重大突破。

🔹 ETH 到底是什么？
ETH 全称 Exponential Time Hypothesis（指数时间假设），由 Impagliazzo、Paturi 等人在 2001 年前后提出。
简单来说，它认为对于经典的 3-SAT 问题，不存在亚指数时间算法。
也就是说，随着变量数量增加，最坏情况下求解问题所需的时间必然呈指数级增长，无法通过算法设计将其降低到亚指数级。
过去 20 多年，ETH 一直是计算复杂性理论的重要基础。图论、计算几何、参数化算法等领域，大量关于算法时间下界的研究都建立在这个假设之上。

🔹 OpenAI 到底突破了什么？
根据论文，OpenAI 给出了一种确定性算法，可以在亚指数时间内，精确计算任意固定 k≥2 的 k-CNF 公式有多少组满足条件的赋值，而且只需要多项式空间。
这已经足以推翻 ETH。
更厉害的是，这个算法不只是判断 SAT 问题有没有解，而是能精确计算所有解的数量，也就是更难的 #SAT 计数问题。
论文的核心思路是利用代数方法，将原本难以拆分的计算转化为可以分组处理的问题，再通过多项式插值恢复最终结果。

🔹 这意味着什么？
影响确实非常大。
① 多个经典假设被推翻。 如果证明成立，ETH、SETH、#ETH、Gap-ETH 等复杂性假设都将不再成立。
② 大量算法下界需要重新审视。 过去许多研究基于 ETH、SETH 证明某些算法不可能更快，现在这些条件性结论需要重新评估。当然，不代表所有下界都自动失效。
③ 打开新的算法研究空间。 论文还给出了独立集、图着色、完美匹配计数等问题的新算法结果。
不过，这并不意味着 P=NP 被证明了。新算法仍然是亚指数时间，而不是多项式时间。

另外，这个证明目前还未获得学术界的最终确认。还是再让子弹飞一会。

#OpenAI #ETH #人工智能 #AI数学