← 返回 Siami 首頁

OpenAI 推倒演算法理論的支柱:ETH 指數時間假設被證偽,3-SAT 首次有次指數演算法

▲ 849 💬 376
OpenAI 推倒演算法理論的支柱:ETH 指數時間假設被證偽,3-SAT 首次有次指數演算法

編按:本文綜合整理自 OpenAI 官方公告〈Working with academic communities to build scientific understanding〉、OpenAI 論文預印本〈The Exponential Time Hypothesis is False〉、OpenAI Lean 形式化說明文件 378.md、Scott Aaronson 部落格〈Podcasts about the Topic: Part II〉、The Verge:OpenAI announces three big science discoveries、Gizmodo:OpenAI Trumpets 3 More Math and Science Results、Kingy.ai:OpenAI’s Science Claims: Kakeya, ETH and Quantum Fields Explained、CS Proofs 影片:The Exponential Time Hypothesis Is False? OpenAI’s Claimed Subexponential #SAT Algorithm, Explained 與 Hacker News 討論串(849 分、376 則回覆),並加入 Siami 編輯部觀點與分析。

2026 年 10 月 26 日,OpenAI 一次公布了三項科學發現,其中一項直接抽掉了演算法理論的一根大樑。

那篇預印本的名字寫得很直白——《The Exponential Time Hypothesis is False》(指數時間假設為假)。作者欄位寫的是「OpenAI」,但論文自己說得更清楚:這是一份「由一個未公開的 OpenAI 內部模型產生的數學手稿」。它不是一篇「做了一組實驗」的報告,而是一篇宣稱推翻了一個四分之一世紀以來業界共識級假設的數學論文。

這件事的重量,需要先從 ETH 是什麼講起。

ETH:被相信了二十年的「SAT 不可能更快」

ETH(Exponential Time Hypothesis,指數時間假設) 是計算複雜度理論裡最被廣泛引用的假設之一。它主張:在最壞情況下,決定一個有 n 個變數的 3-SAT 公式是否可滿足(存在一組指派讓所有子句同時成立),至少需要 2^Ω(n) 的時間。

3-SAT 是 NP 完全問題的原型,整個 SAT 求解器產業的理論根基都與它脫不了關係。ETH 由 Impagliazzo 與 Paturi 在 2001 年正式提出(論文引用編號 [IP01],出自 Journal of Computer and System Sciences 62(2)),並在往後二十多年被拿來當「條件式下界」的基石——意思是:如果你證明了某個問題「至少需要這麼難」,只要 ETH 還站著,這個下界就自動成立。

它撐起了相當大一片理論地圖:

  • 圖論領域的最大 Clique、最小支配集等問題的下界
  • 計算生物學裡的問題難度推導
  • 資料庫理論與計算幾何的條件式下界
  • 3SUM、全對全最短路徑等細粒度複雜度問題的「不可改進」論證

換句話說,ETH 就像一根柱子,整個演算法理論的一整面牆靠著它。


這次被推翻的東西,到底有多大

論文的定理 1.1 給出:對每個固定的 k ≥ 2,存在一個決定性(deterministic)演算法,可以精確計數(不只是判斷有解無解)任意寬度 k 的 CNF 公式的滿足賦值總數。在 n 個變數、m 個子句的公式上,該演算法使用多項式空間,執行時間為:

(n + m)^O_k(1) · 2^(n log log n / √log n)

技術核心來自一個精巧的思路。先看「每個變數最多出現在三個子句中」的受限情況:此時所有子句多項式的乘積次數最多只有 3n,於是可以用插值法從對小組變數的求和中,反推精確的總數。關鍵是共享線性摘要——用一組低次數的線性形式取代原始變數,讓不同變數群組之間只透過少數「量測值」互相影響,於是各群組就能分開計算。附錄 D 再用張量收縮(tensor contraction)把比較寬鬆的上界收緊成定理裡那個漂亮的形式。

把 k 固定在 3,這個演算法就直接推翻了 ETH。而連帶被掃掉的還有一整排假設。論文的相關工作章節明白寫著:定理 1.1 同時否定 ETH、SETH、Gap-ETH 與 NSETH。

  • SETH(強指數時間假設):更嚴格,主張 k-SAT 需要 2^(n(1−o(1))) 時間
  • Gap-ETH:ETH 的強化版,涉及近似解的界
  • NSETH:非確定性版本,主張有某個固定 k 的 k-CNF 不滿足性問題無法用 2^(1−ε)n 解決
  • #ETH:計數版本——精確計數 3-SAT 賦值需要 2^Ω(n) 時間

而且連有界錯誤的隨機化版本(ETH、SETH、Gap-ETH 的隨機版)也一併被推翻。論文同時說明這不與正則分解(regular resolution)等受限證明系統的無條件指數下界衝突——兩者不在同一個層次。

其他幾個值得一提的連帶結果:

  • 推論 1.2:給出任意精確度的 Max-k-SAT 近似演算法,時間同樣是次指數
  • 推論 1.3:圖的獨立集數、q-著色數、完美匹配數,都能在 2^o(v) 時間與多項式空間內精確計算
  • 推論 1.4:存在一個語言 L 屬於 E^NP,其電路複雜度下界為 C_L(n) > c·√(n log n)(對無窮多 n 成立)——這是極不平凡的電路下界成果

Lean 形式化:這次連「驗證」都一起交出來

這份工作的特殊之處,不只是給出演算法,而是連形式化驗證都一併公開。

OpenAI 的 GitHub 倉庫 openai/math 裡,Lean’s OAI/Algorithms/SubexponentialSAT/ 目錄下有整整 1000 個 .lean 檔案——從 SubexpMainBoot 到 SubexpMainCoefficientsSelected,把整個演算法的每一步都拆成可機器檢查的推導。

形式化說明文件 lean/docs/378.md 明確標註了範圍:Lean 證明的是在時間 (L+1)^O_k(1) · 2^(O_k(n(log log n)²/√log n)) 內、由決定性機器精確計數滿足賦值,且每一步走過的磁帶格數都有上界。論文 10 月 25 日修訂版給出的是更緊的 2^(O_k(n log log n/√log n))。

Hacker News 上有人翻到 ComparatorChallenges/SubexponentialSAT.lean 結尾看到 sorry 而困惑,另一位網友 ollin 解釋得很清楚:那個檔案只是命題陳述(用 sorry 佔位,好讓外部專家能獨立重述命題),真正的證明散在 Algorithms 資料夾那上千個檔案裡,最終定理則在 Main.lean。這是 OpenAI 這套 Lean 倉庫一貫的設計。

時間線也值得記下:

  • 10 月 16 日 — AI 找到 ETH 反例的自然語言版本
  • 10 月 17 日 — 完成 Lean 形式化
  • 10 月 26 日 — 公開預印本與 Lean 程式碼

兩天內從「自然語言反例」到「機器可檢查的定理」,這個速度本身就是訊息。


為什麼這件事重要

為什麼這件事重要:ETH 從來不只是「一個假設」,它是整個演算法理論用來說「某件事做不到」的通行證。過去二十年,學界證明「這個問題至少要這麼難」時,最省事的做法就是引用 ETH。當 ETH 倒了,那些結論不會自動全部失效(很多下界有更弱的替代假設支撐,例如最長共同子序列與正則表示式匹配的不可改進論證可以改用正交向量猜想 OVC),但支撐它們的柱子被抽掉了——每一篇依賴 ETH 的論文,都必須重新檢視自己的論證是否還成立。論文自己在相關工作章節裡點名了受影響的領域:圖論的最大 Clique 與分割子圖同構、資料庫與計算幾何、3SUM 與全對全最短路徑的細粒度下界,以及判定有向圖直徑近似的 SETH 界限。

更深一層的意義在於這是 AI 第一次在計算複雜度理論的核心地帶取得結構性突破。過去兩年 AI 做數學的成果大多集中在偏組合的領域(例如局部平滑猜想與 Kakeya 猜想)。這次不同:ETH 是演算法理論、密碼學與理論計算機科學的共同基礎,撼動它的後果會外溢到資安研究。Hacker News 網友 svat 引述了驗證團隊成員 Ryan Williams 的說法:OpenAI 內部模型最先確認的一件事,就是現有密碼系統並未因此被攻破——短時間內,密碼學沒有受到實質影響。

對 AI 研究本身,這也是一場方法論的示範:先讓模型自由找反例,再立刻用 Lean 形式化鎖死,再交給外部專家驗證。這三段式的速度與嚴謹度,是傳統數學家小組工作做不到的——至少在這個案例裡,兩週內完成了一次百年級別的假設翻案。

數據解讀與質疑

數據解讀與質疑:先把最容易誤讀的地方講清楚。「ETH 為假」不等於「P = NP」,這兩件事之間還隔著一大段。論文自己寫了一條明確的界線:2^o(n) 這種執行時間界限無法在一般多項式時間歸約下傳遞(需要 2^n^o(1) 才夠),所以這個結果不表示一般 NP 問題有次指數演算法。Hacker News 上 jibalt 與 mswphd 的追問正是這個點:把 3-著色問題轉成 SAT 實例,規模可能膨脹到 n²,於是 2^(n²/√log(n²)) 依然是超指數。論文在推論 1.3 裡能拿到圖論的次指數結果,是因為編碼保持了計數——那是刻意設計的,不是白撿的。

第二個誤讀是實用性。UC San Diego 的研究生 Eric Binnendyk 在 Scott Aaronson 的部落格留言說得很直白:他手上一篇即將發表的論文有一條 ETH 下界,當天收到通知後必須緊急修改。而 Joshua Zelinsky 也在同一串留言裡算了一筆帳——exp(n/√log n) 這個量級仍然差於任何 L-notation 的界限,拿來分解整數不會贏過 number field sieve,拿來解圖同構也不會贏過現有最佳演算法。換句話說,這個演算法在可見的未來不會變成一個更快的 SAT 求解器。它的價值在於理論邊界被推到了哪裡,不是明天的工程加速。

第三個必須記錄的是驗證狀態。Lean 形式化的存在意味著「陳述與推導沒有形式錯誤」,但形式化證明本身不等於「命題在數學上被接受了」。這也是為什麼 OpenAI 這次特別安排了三個人領軍的外部團隊來把關,而且這三個人的分量極不尋常:Russell Impagliazzo 與 Ramamohan Paturi 正是 ETH 本身的原始提出者,第三位 Ryan Williams(MIT) 則是曾經推翻 MA-SETH(Merlin–Arthur 版 SETH)、並長期在演算法與下界之間搭橋的人。由 ETH 的提出者來驗證 ETH 的反例,這種安排本身就是對可信度最有效的補強。

但社群的反應也提醒了幾件事。第一,專家社群對「AI 已經在理論數學上取得這種成果」的信任基礎,本來就還在建立中。Scott Aaronson 本人的說法是:「看到這個消息,我把自己認為 P=NP 的個人機率從 3% 上調到 5%。」另一位網友則說對他而言是 10% 變 20%。這種用機率表達的保留,說明社群正在消化,但沒有到歡呼的程度。第二,驗證工作才剛開始。OpenAI 承諾資助一場專門會議來理解這項成果對整個領域的影響,並邀請社群組織「公開審查」(open examination)——這意味著現在流通的是一個已經形式化、但還沒有被整個領域審完的主張。第三,利益結構的問題並沒有因為形式化而消失。OpenAI 自己的數學顧問小組 AGMAI 就在前一天公開建議:AI 公司不應該採用「先指定特定幾位學者優先取得成果」的做法,因為這會造成資訊不平等、借用他人聲望,以及挑選偏差。OpenAI 這次對電腦科學成果採取的正是「組外部協作團隊 + 同時公開原始資料」的策略,而 AGMAI 的批評正好打在這個點上。OpenAI 對此列出四項原則:透明、不追求學術名分、給予外部團隊成果署名、參與獨立且不代言雙方。

所以比較誠實的定位是:**這是一個已經通過機器檢驗、並由最有資格的專家接手獨立驗證的成果;它在數學上還沒有完成驗證,在工程上短期內也不會有任何用武之地。**至於它最終會不會被接受為定理、會不會在五年後變成教材裡的一行字,現在誰也說不準。

三項成果,開放不同的發布策略

順帶一提,OpenAI 這次同時公布的三項發現,用的是三套不同的發布策略,背後的考量很值得玩味:

  • 數學:局部平滑猜想(進而解出所有維度的 Kakeya 猜想與 Stein 限制猜想)——直接公開 AI 原始輸出,讓研究者自行組織解讀
  • 計算機科學:ETH 為假——組成外部協作團隊解讀,同時立即公開 AI 輸出
  • 物理:四維量子色動態學與標準模型完備性的存在性證明——交由外部團隊主導,暫不釋出 AI 產物

物理那條線由 2004 年諾貝爾物理獎得主 David Gross 領軍,團隊成員還包括 Michael Douglas、Arthur Jaffe、Igor Klebanov、Nikita Nekrasov。數學那條線則是 10 月 6 日那波「釋出數百份手稿」的延續,AI 輸出在 10 月 18 日取得,隔天就完成 Lean 形式化。

同一份公告裡,OpenAI 明確說明了自己的立場:把這些手稿視為**「原始研究資料」**(raw research data),而外部協作的角色是把原始資料轉成「科學理解」。他們也承認這套做法有取捨——選擇最初的「牧羊人」必然塑造了誰會先參與,也製造了資訊不對稱。


接下來該盯什麼

真正的驗證與消化,需要時間。可以先列幾個具體的觀察點:

  1. Impagliazzo、Paturi、Williams 團隊的公開審查結論何時出爐 —— 這是判斷「定理成立」與「主張成立」的分水嶺
  2. 論文會不會被正式發表在期刊或會議上 —— 走完匿名審稿流程是另一種形式的外部背書
  3. 依賴 ETH 的既有下界論文有多少需要重做論證 —— 這決定了這次成果的實際「破壞力」有多大
  4. 會不會有人把這個演算法工程化 —— 目前看來不切實際,但若有人找到常數因子上的實用改進,產業影響會立刻放大
  5. AGMAI 與 OpenAI 在發布倫理上的角力 —— 這條線的走向,可能比 ETH 本身更能決定未來 AI 做科學的樣貌

對台灣的開發者與研究者而言,一個更實際的提醒是:AI 產出的數學成果正在以「已形式化、可公開檢驗」的形式大量湧現。過去要讀懂一個新定理得靠信任期刊的審稿人;現在多了一條路徑——直接去讀 Lean 原始碼。openai/math 這個倉庫會是一個值得長期追蹤的資源。

延伸閱讀

網友熱門留言 (10)

#1 Hacker News 網友 lisper 0
這感覺很巨大,雖然還不到 P=NP,但已經在同一個量級了。我有漏掉什麼嗎?
#2 Hacker News 網友 odyssey7 0
不是「還不到 P=NP」,而是「確實不是 P=NP」。話雖如此,依然是了不起的成就。
#3 Hacker News 網友 jibalt 0
這並不是 NP ≠ EXP 的證明。NP 可以多項式時間歸約到 3-SAT,而 3-SAT 是次指數時間的,這兩件事加起來並不推出 NP 是次指數的——歸約本身的成本可能就足以把次指數又推回指數。
#4 Hacker News 網友 cochne 0
它不表示 NP 是次指數的,只表示 3-SAT 是。轉換到其他問題時仍可能變成指數。論文本身也說了:2^o(n) 這種執行時間界限無法在一般多項式時間歸約下傳遞,需要 2^n^o(1) 才行,所以這個結果並不表示一般 NP 問題有次指數演算法。
#5 Hacker News 網友 mudita 0
Scott Aaronson 在他的部落格上說:「看到這個消息,我把自己認為 P=NP 的個人機率從 3% 上調到 5%。」
#6 Hacker News 網友 zeroonetwothree 0
我沒有 Scott 那麼聰明,但對我來說比較像是 10% 變 20%。我們有針對這件事的預測市場嗎?
#7 Hacker News 網友 jaggederest 0
這推翻了幾個被廣泛依賴的假設:強指數時間假設,以及這篇文章標題裡的指數時間假設。它不是說這些問題變得容易了,但確實證明它們比過去認為的容易得多。十年前如果有人發表這種東西,而且撐得住檢驗,他幾乎肯定會是諾貝爾獎或菲爾茲獎等級的候選人。
#8 Hacker News 網友 thatoneengineer 0
假設 P ≠ NP(而且這個 NP ≠ EXP 的證明站得住腳),那麼 NP 必須增長得多快的下一個「最自然」候選是什麼?這篇論文看起來只給出 Ω(2^(n/√log(n))),還多了幾個修飾因子,這答案實在令人失望。
#9 Hacker News 網友 pcstl 0
這證明了 EXP ≠ NP,是比 P ≠ NP 更強的主張。它顯示 NP 也許沒有想像中離 P 那麼遙遠。它究竟能不能用某種「巨大腦」的方式被化約到 P,或這能被證明不可能,還有待觀察。但它確實是朝 P 與 NP 問題答案的實質進展。
#10 Hacker News 網友 mswphd 0
實務上,多項式時間歸約會放大問題實例的規模。假設你把一個有 n 個頂點的三色問題轉成 n^2 大小的 SAT 實例,接著可以在 2^(n^2/√log(n^2)) 的時間內求解——但那不是次指數。