OpenAI 宣布,旗下內部前沿模型於 2026 年 10 月 16 日提出了一份自然語言證明,主張指數時間假說(ETH)並不成立,並於 10 月 17 日將該論述形式化為 Lean 證明。ETH 是計算複雜度理論中廣泛採用的一項猜想,非正式而言,它主張對固定的 k 而言,解決一般 k-SAT 問題所需的時間,會隨變數數量呈指數級增長。OpenAI 的主張聚焦於一種受限 SAT 問題族的次指數時間演算法;若此結果正確,將牽動許多以 ETH 為基礎的條件式困難度結果。
重要的是,要區分三件彼此相關但並不相同的事:(1)ETH 的主張內容,以及它在實際演算法層面排除了哪些可能性;(2)提出的具體反例——一種能在次指數時間內處理固定寬度 SAT 實例的演算法;(3)這對 P 與 NP 等核心未解問題有何影響。這項新主張針對的是第二點:以建構性方法挑戰 ETH 假說,但並不會自動推翻複雜度理論中更廣泛的問題分離圖景。對試圖解讀這則技術消息的實務工作者與投資人而言,這項區別細微卻至關重要。
OpenAI 並未將此事視為定論。該公司已邀請由 ETH 原始提出者 Russell Impagliazzo 與 Ramamohan Paturi,以及 MIT 的 Ryan Williams 領軍的外部團隊,負責推動驗證與獨立審查。他們將統籌社群檢視、評估自然語言論證、稽核 Lean 形式化內容,並確認這項建構是否真的帶來所宣稱的漸近執行時間改善,且沒有隱藏的限制條件。在學界將此主張視為定論之前,獨立審查仍是決定性的一步。
對創辦人、研究人員與產品領導者而言,這件事帶來兩項實際啟示:突破性成果如今可能源自模型輸出,並能迅速透過機器驗證,進而加速構想發展與假說測試;但機器驗證的證明並不能取代領域專業知識。即使形式證明正確,仍可能需要結合脈絡解讀,才能理解其更廣泛的演算法影響、實際效能,以及如何將漸近改善轉化為工程或商業價值。


