OpenAI宣布證偽計算機領域沿用二十多年的重要理論「指數時間假設ETH」

BlockBeats 消息，10 月 27 日，OpenAI 日前宣佈，其 AI 模型「破解」了 ETH——這一消息迅速在科技圈和加密圈引發熱議。但需要特別說明的是，這裡的 ETH 並非加密貨幣領域廣為人知的以太坊（Ethereum），而是計算機科學中一個存在了二十多年的重要猜想：指數時間假設（Exponential Time Hypothesis，簡稱 ETH）。

指數時間假設的核心問題是：那些看起來「特別難算」的問題，到底有多難？

以部分人聽說過的「SAT 問題」（布爾可滿足性問題）為例，它是在問：給你一堆邏輯條件，能不能找到一種賦值讓所有條件同時成立？當問題規模變大時，目前已知最好的辦法基本上只能挨個嘗試可能的答案，時間開銷會隨著規模呈指數級增長——也就是常說的「指數時間」。ETH 進一步斷言，這類問題本質上就無法被大幅加速，不存在真正意義上的「亞指數時間」高效演算法。

這個假設自 1999 年被提出以來，一直是理論計算機科學的重要基石。成百上千篇論文都基於它來證明「某某問題很難」「某某演算法已經接近最優」。如果 ETH 被推翻，就意味著很多我們以為「幾乎不可能更快」的問題，理論上或許存在更好的解法。

OpenAI 此次聲稱，其模型找到了一個確定性演算法，能在亞指數時間內精確統計 k-SAT 問題的解的數量，並用 Lean 進行了形式化驗證。如果這一結果最終經得起專家審查，它將直接動搖指數時間假設。