OpenAI 表示，旗下一款人工智慧模型找到了推翻指數時間假說（ETH）的方法。ETH 是 1999 年提出的電腦科學猜想，與以 ETH 為交易代碼的加密貨幣以太幣（Ethereum），或以太幣共同創辦人 Vitalik Buterin 均無任何關聯。

儘管如此，這項宣布仍在 Crypto Twitter 上引發不少調侃。用戶 Takumi 在 X 上發文稱：「該死，演算法交易員把 $ETH 屠殺了」，Andrew Jiang 則打趣道：「這消息出來之後，Vitalik 一直很安靜。」

此處所指的 ETH 由電腦科學家 Russell Impagliazzo、Ramamohan Paturi 與 Francis Zane 提出。該假說主張，被稱為 3-SAT 的邏輯問題無法比逐一檢視所有變數組合的方式快上太多。在 3-SAT 中，目標是判斷是否存在能滿足一組規則的真假賦值，其中每條規則包含三個變數。

據 OpenAI 表示，數百篇學術論文倚賴這項假說來證明圖論、計算生物學、資料庫與幾何學中的某些問題無法被快速求解。該公司指出，推翻 ETH 可能重新開啟這些任務還能提速多少的問題，並協助研究人員尋找更佳演算法。

「對 ETH 的駁斥重新開啟了這些任務還能提速多少的問題，」OpenAI 在其部落格文章中寫道，「並可能有助於引導尋找更好的演算法。」

OpenAI 這篇 67 頁的論文日期為 10 月 17 日，並於 10 月 25 日修訂，描述了一個確定性演算法（即不使用隨機性的演算法），能以次指數時間計算這類謎題的所有滿足賦值。這意味著工作量隨變數數量的增長速度慢於任何指數函數。由於計算解的數量比判斷是否存在至少一個解更困難，這項結果也順帶解決了判定問題。

OpenAI 表示，其 AI 於 10 月 16 日發現了這項反證，並於 10 月 17 日在 Lean（一種能機械化驗證每個邏輯步驟的軟體）中完成形式化。論文與形式化內容均已發布於 GitHub。OpenAI 表示，此舉延續了本月初發布的 722 份數學手稿，其中僅 162 份附有經電腦驗證的主要結果。正是這種機器可驗證的格式，讓獨立研究者能夠自行核驗論證的每一個步驟。

Impagliazzo、Paturi 與 MIT 教授 Ryan Williams 正主導對該主張的獨立審查。他們在一封公開信中提醒，他們的參與不應被解讀為背書。

「我們的參與不應被視為對該主張的認證，」三人寫道，並補充「如此重要的結果需要審慎、獨立的審查，也需要理解他人能夠重構、質疑並在此基礎上繼續發展。」

OpenAI 表示，參與者並未簽署保密協議，且屬無償工作。該公司也同意公開所有原始資料，並資助一場聚焦於這項結果的會議。

實際影響仍不確定。「找出這類演算法，並將理論進展轉化為實際改進，將需要大量進一步研究，」OpenAI 寫道。論文本身也指出，這項結果並未證明複雜度類別 NP 中的每個問題都能在次指數時間內求解。

這意味著 P 與 NP 問題仍未解決。P 是電腦能夠高效求解的問題類別，而 NP 是其候選解能被高效驗證的問題類別。未解的問題是：答案能被高效驗證的每個問題，是否也都能被高效求解。

Anthropic 於 10 月 26 日加入這場討論，發表了一篇署名 Claude、題為「A 2^o(n) Time Algorithm for 3-SAT」的論文。該程式庫同樣針對 ETH 問題，指出該演算法由一個內部研究用 Claude 模型發現，並補充「這項結果純屬漸近性質，對實際求解公式沒有任何說明」。

Claude 曾於 9 月在 Lean 中形式化費馬最後定理，而數學家 Terence Tao 早已預見這種 AI 成果重疊的可能性，他在 9 月寫道：「我們現在已經看到，光是有人在研究某個問題的傳聞，就足以在原有研究計畫來不及發揮全部潛力之前，引發大量由 AI 驅動的努力將其搶先攻克。」

OpenAI 近來向 Simons Foundation 捐贈的 500 萬美元，將用於資助工作坊、會議與特殊計畫，協助研究人員審視以 AI 產出的結果並在此基礎上繼續發展。

來源：Decrypt