OpenAI、Anthropic稱AI找到3-SAT次指數時間演算法，挑戰25年指數時間假說

OpenAI與Anthropic於10月26日各自宣稱，人工智慧（AI）模型找到了能以低於指數時間求解3-SAT的演算法，因而反證指數時間假說。兩家公司公開了論文與形式化證明。

公布數日後，提出這項假說的Russell Impagliazzo與Ramamohan Paturi，以及長期質疑該假說的麻省理工學院研究者Ryan Williams接受法新社（AFP）訪問。三人談及研究意義、獨立檢視，以及研究者未來的角色。

指數時間假說（Exponential Time Hypothesis，ETH）主張，隨著輸入規模增加，某些計算問題所需的求解時間會呈指數成長。這項假說約在25年前提出，長期作為電腦科學與生物學研究的前提。

兩家公司研究的3-SAT，是判定是否存在一組答案，能同時滿足多項邏輯條件的問題。指數時間假說指出，對最壞情況下含有n個變數的3-SAT，不存在能在2^{o(n)}時間內求解的決定性演算法。

OpenAI公開的論文提出一種決定性演算法，可精確計算k-CNF布林公式的解數。論文初稿於10月17日完成，修訂版標示日期為10月25日；作者欄只列出OpenAI。

Anthropic表示，內部研究使用的Claude模型找到了一種演算法，能在理論計算範圍內以低於指數時間求解3-SAT。該公司公開了由Claude撰寫的論文，以及Lean 4形式化證明。

兩家公司也說明了研究成果的適用範圍。Anthropic指出，這是探討問題規模極大時所需計算量的漸近成果，不代表能快速解決實際問題。OpenAI也在論文中表示，研究結果不代表所有NP問題都有低於指數時間的演算法。

Lean是一種可由電腦檢查形式化證明的工具。兩家公司公開Lean資料，讓外界能檢查證明；但這本身不代表學界的獨立評估已經完成。

這次訪問呈現了假說提出者與懷疑者對同一項成果的不同反應。

Impagliazzo說：「如果是能解釋思考過程的人類發現這項成果，會好得多。」他補充，人類能說明得出答案的過程；有時這個過程和答案本身同樣重要。

Paturi表示，他的第一個反應是驚訝。他說，過去30年以這項假說為基礎的研究，不會因為這次成果發布而失去價值。

Williams說：「我從未完全相信這項假說。」他一直公開質疑這項假說，也認為這次成果支持了他的懷疑。

三位研究者正參與籌組獨立檢視，以評估兩家公司的主張。OpenAI也表示，由Impagliazzo、Paturi與Williams帶領的外部研究團隊將檢視證明。

Paturi表示，拓展研究邊界，以及決定研究方向並推動其發展，仍是人類的工作。他建議學生學習使用這些工具，同時培養自己的判斷力。Williams則說，這個領域正迎來重大變化，但仍值得投入研究。

Impagliazzo擔心，現階段可能形成由AI負責解題、人類負責驗證與說明的分工。他認為，在AI進一步發展之前，這些工作仍會留給人類研究者。

Paturi指出，若強大的研究工具集中在企業手中，誰能參與研究、誰能先使用工具，以及研究題目由誰決定，都會成為問題。他說：「企業發布的成果不能取代同儕審查。」指數時間假說的縮寫與以太幣（ETH）的代號相同，但只是縮寫相同，這項研究與以太幣無關。

Impagliazzo表示，這項成果本身不構成資訊安全威脅。他補充，後續研究可能使人們需要更強的加密技術，但這不代表現有密碼已遭破解。