
封面為 AI 生成的概念示意;迷宮與光路是比喻,不是算法結構、真實實驗或性能結果。
- 解讀日期:2026-10-27
- 資料截止:2026-10-27 20:31:22(北京時間,Asia/Shanghai)
10 月 26 日,OpenAI 宣佈其內部模型給出了指數時間假設(ETH)的反駁,並公開自然語言手稿及 Lean 形式化材料。這是值得認真檢查的重大主張:它可能改變計算機科學對一類問題“究竟有多難”的判斷。不過,公開材料、機器核查與學界理解是不同環節。今天最有價值的問題,是這份主張已經提供了什麼,又把哪些工作留給了研究者。官方公告
要推翻的,是怎樣一道計算邊界?
先想像一組開關:每個開關只能取真或假,每條規則要求幾個條件至少滿足一個,全部規則又必須同時成立。3-SAT 問的,就是每條規則最多涉及三個文字項時,是否存在滿足全部規則的開關配置。這裡的文字項可以是變量,也可以是它的否定。
ETH 並非說必須逐一試完所有配置,而是斷言:以變量數衡量,最壞情況下無法把這類問題普遍降到次指數時間。次指數可記作 ,意思是指數部分相對變量數的比例會隨規模增大趨於零,另需計入讀取、處理輸入的開銷。手稿摘要及引言
這份手稿聲稱完成的任務更強:對於固定子句寬度的公式,精確計算滿足條件的配置總數,並使用多項式空間。只要總數大於零,就能回答是否有解。取寬度為三,便觸及 ETH 的核心。因此,值得關注的是隨規模增長的理論上界,而非某個測試集多答對了幾題。
手稿給出了什麼思路,日期又該怎樣讀?
按手稿的方法概覽,算法先把邏輯條件寫成多項式,再組織精確計數。一個直觀出發點是:如果變量能夠分成互不牽連的小組,就可以分別計算,再合併結果。真正困難的是跨組依賴;作者嘗試用少量共享的線性摘要傳遞這些依賴,配合插值等代數方法恢復總數。這只是幫助理解的入口,並非對完整證明的替代。手稿第 2 節
時間線同樣不能壓縮成“今天發現”。OpenAI 稱自然語言反駁產於 10 月 16 日,次日完成形式化;公開 PDF 標註 10 月 17 日、10 月 25 日修訂;公告日期是 10 月 26 日。公告未給出精確時區時間,本文不據此斷言它發生在過去二十四小時內。公告時間線
這些材料也沒有給出本文能夠據以確認的同行評審錄用信息。它們應作為公開研究手稿和待審查證明閱讀。
Lean 覆蓋的上界,與手稿並不完全相同
Lean 是證明助手:把命題與推導寫成形式語言,再檢查其邏輯依賴。它為審查提供了比一段流暢說明更具體的對象,但仍需要人判斷形式命題是否準確表達了原問題。
OpenAI 的範圍說明明確區分了兩個層次:Lean 覆蓋規範編碼輸入上的精確計數、次指數時間和多項式空間;10 月 25 日手稿則給出更緊的時間上界。兩者指數項相差一個雙重對數因子,手稿在子句數至多為變量數固定倍數時還有更強界限。不能把手稿最好的式子直接標成“全部已由 Lean 驗證”。形式化範圍說明
範圍說明中的較寬鬆上界仍是次指數的,所以這種差別本身並不推翻其反駁 ETH 的方向。審查應繼續追問:編碼長度如何計入成本,機器模型如何定義,量詞是否要求同一個算法處理全部合格輸入。本文核對了範圍說明和公開命題文件,但沒有運行證明檢查器,也沒有逐步驗證整份證明。
另一份證明,不能自動充當複核報告
截至資料截止時,Anthropic 的公開倉庫也提供了 Claude 產生的次指數 3-SAT 算法手稿與形式化材料。其說明同樣強調結果是漸近理論結論,並明確提醒:機器檢查證明,並不自動檢查形式命題是否與論文敘述一致。本文讀取的是該倉庫說明,尚未完成兩份證明的技術比較。Anthropic 原始材料
這增加了可研究的材料,卻不能簡單累計為“兩次獨立驗證”。另一個團隊提出同類結論,與外部研究者成功複核第一份論證,是兩種證據。它們是否共享關鍵思路、是否存在相同盲點,仍值得比較。
Russell Impagliazzo、Ramamohan Paturi 與 Ryan Williams 在公開信中說明,參與組織工作不應被當作對主張的認證。他們邀請社區檢查論證、解釋方法、研究後果,也討論如何認可核查與簡化證明的勞動。致理論計算機科學社區的公開信
這封信提供的是審查立場,不是已完成的正確性結論。本次檢索未找到足以據此報告“獨立審查已經完成”的材料。
科研讀者現在可以關注什麼?
首先,次指數仍可能比任何多項式都增長得快,因此這一主張不能被讀成已經解決 P 與 NP。其次,手稿自己提醒:一般多項式歸約可能放大變量規模,不能由此推出所有 NP 問題都有次指數算法。理論上界也沒有給出實際輸入上的加速比。手稿第 2 頁
即使反駁成立,過去寫成“若 ETH 成立,則某算法不存在”的條件定理,也不因此變成錯誤證明。失去的是直接把前提當作可信依據的理由;要為目標問題設計更快算法,還需要控制歸約方向與規模。這是閱讀既有論文時應保持的邏輯區分。
本文的判斷是:這次事件的重要性足以推動認真審查,但當前最值得等待的成果,是可重建的核查記錄、形式命題與自然語言命題的逐項對應,以及能被其他研究者理解和使用的簡化論證。當這些材料出現時,我們才能更清楚地區分:AI 提出了一個重要答案,還是已經幫助學界建立了一份可靠的新知識。
參考資料
- OpenAI:Working with academic communities to build scientific understanding,2026-10-26;已讀公告正文。
- The Exponential Time Hypothesis is False,標註 2026-10-17、2026-10-25 修訂;已讀摘要、引言第 1–5 頁與方法概覽第 7–8 頁,視覺核對第 2 頁主定理,未審完整證明。
- OpenAI:ETH 的 Lean 形式化範圍說明,頁面未標獨立發佈日期;已讀全文,並核對其鏈接的命題文件,未執行驗證。
- Anthropic:A subexponential time algorithm for 3-SAT,倉庫說明,頁面未標獨立發佈日期;已讀說明全文,未讀完整論文或運行證明。
- Impagliazzo、Paturi、Williams:Message to the TCS Community on ETH,文檔未標獨立日期;通過公開文本導出讀到正文,10 月 26 日媒體已有鏈接。該信是審查組織者的一手立場材料。
作者作品推廣
除了寫技術博客,我也在做一些讓日常更有條理的小工具。以下是我獨立開發的兩款 App,屬於作者自有作品推廣,歡迎瞭解:
- 日常收支小記:記錄日常收支,安排預算與儲蓄目標,讓每一筆錢的去向更清楚。在 App Store 瞭解。
- 一事微光:根據當下的時間和精力選擇一個小行動,記錄完成後的感受與發現,讓日常行動與復盤更容易開始。在 App Store 瞭解。
更多技術文章與個人作品,歡迎訪問我的網站:zffjzz.top。