OpenAI宣布证伪计算机领域沿用二十多年的重要理论「指数时间假设ETH」

contact@theblockbeats.org (律动BlockBeats)

10 月 27 日，OpenAI 日前宣布，其 AI 模型「破解」了 ETH——这一消息迅速在科技圈和加密圈引发热议。但需要特别说明的是，这里的 ETH 并非加密货币领域广为人知的以太坊（Ethereum），而是计算机科学中一个存在了二十多年的重要猜想：指数时间假设（Exponential Time Hypothesis，简称 ETH）。

指数时间假设的核心问题是：那些看起来「特别难算」的问题，到底有多难？

以部分人听说过的「SAT 问题」（布尔可满足性问题）为例，它是在问：给你一堆逻辑条件，能不能找到一种赋值让所有条件同时成立？当问题规模变大时，目前已知最好的办法基本上只能挨个尝试可能的答案，时间开销会随着规模呈指数级增长——也就是常说的「指数时间」。ETH 进一步断言，这类问题本质上就无法被大幅加速，不存在真正意义上的「亚指数时间」高效算法。

这个假设自 1999 年被提出以来，一直是理论计算机科学的重要基石。成百上千篇论文都基于它来证明「某某问题很难」「某某算法已经接近最优」。如果 ETH 被推翻，就意味着很多我们以为「几乎不可能更快」的问题，理论上或许存在更好的解法。

OpenAI 此次声称，其模型找到了一个确定性算法，能在亚指数时间内精确统计 k-SAT 问题的解的数量，并用 Lean 进行了形式化验证。如果这一结果最终经得起专家审查，它将直接动摇指数时间假设。