OpenAI 宣布模型破解指数时间假设

OpenAI 日前宣布，其 AI 模型破解了计算机科学中沿用二十多年的猜想指数时间假设，英文简称 ETH，并非以太坊。该假设关注特别难算的问题到底有多难，并以布尔可满足性问题 SAT 为例：给定一组逻辑条件，是否存在一种赋值使所有条件同时成立。问题规模变大时，已知最好办法基本只能逐个尝试可能答案，时间开销随规模呈指数增长。指数时间假设进一步断言，这类问题本质上无法被大幅加速，不存在真正意义上的亚指数时间高效算法。

该假设自 1999 年提出以来，一直是理论计算机科学的重要基石，大量论文基于它证明某些问题很难、某些算法已接近最优。若指数时间假设被推翻，意味着许多被认为几乎不可能更快的问题，理论上或许存在更好解法。OpenAI 声称，其模型找到一个确定性算法，能在亚指数时间内精确统计 k-SAT 问题的解的数量，并用 Lean 进行了形式化验证。若该结果最终经得起专家审查，将直接动摇指数时间假设。