指數一層層被壓平 左邊寫著 3-SAT、窮舉的 2 的 n 次方和新結果 2 的 o(n) 次方。右邊是一組從同一點出發的指數曲線,最陡的是 2 的 n 次方,往下每一條的指數都乘以 11/12,最平的一條是強調色;背景是一片網格節點。 2ⁿ ×(11/12) … 3-SAT · n 個變數 2^δn 2^o(n) δ → 0 ETH, 1999–2026

We refute the Exponential Time Hypothesis (ETH) by presenting a deterministic algorithm for 3-SAT on n variables that runs in 2o(n)2^{o(n)} time.

這是 2026 年 10 月 27 日公開的一篇預印本(還沒經過期刊審稿、先放到網上的論文)摘要的第一句,作者一欄寫的是 Claude1。翻譯過來是:“我們給出一個在 2o(n)2^{o(n)} 時間內解決 nn 個變數的 3-SAT 的確定性演算法,從而推翻了指數時間假說(ETH)。”前一天,OpenAI 也在 GitHub 上放出了一篇標題直接叫《指數時間假說是錯的》的論文2。轉到中文社交媒體上,標題很快變成了“AI 推翻三十年計算機難題”“P=NP 又近了一步”“密碼學要變天”。

這句話裡幾乎每個詞都需要解釋:3-SAT 是什麼?“指數時間”指什麼,憑什麼是一個“假說”?2o(n)2^{o(n)} 是快還是慢?它和大名鼎鼎的 P vs NP 又是什麼關係?兩家 AI 是怎麼做到的,結論靠得住嗎?

這些問題都可以從一道簡單的邏輯題講起。

一、一道邏輯謎題:什麼是 SAT

安排一次聚會

假設你要請三位朋友 A、B、C 來家裡,但他們之間有些講究:

  1. A 和 B 至少要來一個,不然沒人張羅。
  2. A 和 C 不能都來,他們倆合不來。
  3. 如果 B 來,C 也得來,B 一個人不肯來。
  4. A 和 C 至少要來一個,因為只有他們會做飯。

有沒有一種邀請方案,讓四條要求同時滿足?

每位朋友只有“來”和“不來”兩種狀態。我們用一個變數表示,來記作 1,不來記作 0。這種只能取 0 和 1(也可以說“真”和“假”)兩個值的變數叫布林變數,名字來自 19 世紀的數學家布林(George Boole),他最早把邏輯寫成了代數。下面用小寫的 a,b,ca,b,c 分別表示 A、B、C 來不來。

再看每條要求。第 1 條是“A 來,或者 B 來”,寫成 a∨ba \lor b,符號 ∨\lor 讀作“或”,兩邊只要有一個成立,整句就成立。第 2 條“A 和 C 不能都來”換個說法是“A 不來,或者 C 不來”。“不來”是“來”的反面,用 ¬a\lnot a 表示,讀作“非 aa”,a=1a=1 時 ¬a=0\lnot a=0,反之亦然。於是第 2 條寫成 ¬a∨¬c\lnot a \lor \lnot c。第 3 條“如果 B 來,C 也得來”,等價於“B 不來,或者 C 來”,寫成 ¬b∨c\lnot b \lor c。第 4 條是 a∨ca \lor c。

像 a∨ba \lor b 這樣,幾個變數(或它們的反面)用“或”連起來的一句話,叫一個子句。四條要求必須同時成立,用“且”(∧\land)把它們連起來:

(a∨b)∧(¬a∨¬c)∧(¬b∨c)∧(a∨c)(a \lor b)\land(\lnot a \lor \lnot c)\land(\lnot b \lor c)\land(a \lor c)

“一串子句用‘且’連起來”的這種寫法叫合取正規化(CNF,合取就是“且”的意思)。現在問題可以說得很精確了:給定一個合取正規化,有沒有一組 0/1 取值,讓它整體成立?這個問題叫可滿足性問題,英文 Boolean Satisfiability,縮寫就是 SAT。如果每個子句最多隻有 3 個變數,就叫 3-SAT。我們的聚會問題每句只有 2 個變數,當然也算 3-SAT 的一個例子。

最笨的辦法:挨個試

三個人,每人兩種狀態,一共 2×2×2=82\times2\times2=8 種方案。全部列出來檢查一遍:

8 種邀請方案逐一檢查(1 = 來,0 = 不來)
abc哪條要求沒滿足結果
000第 1 條(A、B 都沒來)不行
001第 1 條不行
010第 3 條(B 來了 C 沒來)不行
011都滿足可以
100都滿足可以
101第 2 條(A、C 都來了)不行
110第 3 條不行
111第 2 條不行

檢查一個方案只要看四條要求;找出可行方案,這裡靠的是把 8 種都試一遍。

表 1 · 聚會問題有兩個解:只請 A,或者請 B 和 C

答案是有兩種方案:只請 A,或者請 B 和 C。

這張表也顯示出 SAT 的一個特點。拿到一個方案,檢查它對不對很容易,四條要求逐條看一遍就行;但要找到一個對的方案,最直接的辦法只有挨個試。

人數一多,挨個試就不行了。每多一個變數,方案數就翻一倍,nn 個變數就有 2n2^n 種。n=50n=50 時大約是 101510^{15} 種,一臺每秒檢查一萬億(101210^{12})種的計算機要算 19 分鐘;n=100n=100 時約 1.3×10301.3\times10^{30} 種,要算 400 億年,是宇宙年齡的三倍。實際中的 SAT 問題常有幾千、幾萬個變數。

為什麼要關心這樣一道謎題?因為大量現實問題都能寫成 SAT。排課(某老師週一上午不能有課,兩門課不能同時在一間教室)、檢查晶片設計有沒有錯、填數獨,都可以把“選或不選”“是或不是”設成布林變數,把規則寫成子句。SAT 會解了,這些問題就都會解了。

那麼,除了挨個試,到底有沒有本質上更快的辦法?要討論“更快”,得先說清楚怎麼比較快慢。

二、演算法的快與慢

數步數,而不是看秒錶

同一個演算法,在新電腦上跑得快,在舊電腦上跑得慢,所以電腦科學不用秒錶衡量演算法,而是看步數怎樣隨問題規模增長。問題規模記作 nn,對 SAT 來說就是變數個數。

有的演算法的步數是 n2n^2、n3n^3 這樣的冪函式,或者幾個冪函式相加,這叫多項式時間;有的是 2n2^n 這樣的指數函式,叫指數時間。這兩類函式在 nn 小的時候看不出差別,nn 一大差距就大得離譜:

多項式與指數:步數隨 n 增長
nn²n³2ⁿ
101001,0001,024
204008,000約 100 萬
502,500125,000約 10¹⁵
10010,0001,000,000約 1.3 × 10³⁰
每秒 10¹² 步的計算機,n = 100 時要算
用時不到 1 微秒1 微秒約 400 億年
表 2 · n = 10 時三者差不多;n = 100 時多項式還是一眨眼,指數已經比宇宙年齡還長

多項式時間的演算法,nn 翻一倍,n3n^3 也只是變成原來的 8 倍,電腦快一點就追得上。指數時間的演算法,nn 只要加 1,步數就翻倍,電腦快一千倍也只能多處理 10 個變數。所以大家通常把“有多項式時間演算法”當作“能高效解決”的標準。

P、NP 和 NP 完全

按這個標準,問題可以分成幾類。

能在多項式時間內解決的問題,叫 P 類(P 是 Polynomial,多項式)。比如把一串數從小到大排好序、在地圖上找兩點之間的最短路線,都屬於 P。

答案能在多項式時間內檢查的問題,叫 NP 類。SAT 就屬於 NP:給你一組取值,逐個子句檢查一遍,步數和公式長度成正比。NP 的全稱是 Nondeterministic Polynomial(非確定性多項式),名字來自一種假想的“能同時猜遍所有答案”的機器,我們只要記住它的意思是“答案容易檢查”就夠了。能解決的問題當然也能檢查答案,所以 P 包含在 NP 裡面。

NP 裡面最難的一批問題叫 NP 完全問題。1971 年 Cook 證明了 SAT 就是其中之一,1972 年 Karp 又找出了一大批。它們“最難”的含義是:NP 裡的任何問題,都能在多項式時間內改寫成一個 SAT 問題,答案保持不變。這種改寫叫歸約。比如數獨可以改寫成 SAT:每個格子填每個數字設一個變數,“每格恰好一個數”“每行不重複”等規則寫成子句。既然所有 NP 問題都能這樣改寫,只要 SAT 有了多項式時間演算法,所有 NP 問題就都有了。3-SAT 也是 NP 完全的,因為再長的子句,引入幾個輔助變數後都能拆成每句不超過 3 個變數的幾個子句,可滿足性不變。

P、NP 與 NP 完全 NP 是答案容易檢查的問題,裡面左邊是能高效解決的 P 類,例如排序和最短路線;右邊是 NP 完全問題,例如 SAT、3-SAT 和數獨。任何 NP 問題都能歸約成 SAT。 NP:答案能在多項式時間內檢查的問題 都能歸約成 P:能高效解決 多項式時間 排序一串數 地圖上的最短路線 判斷一個數是不是質數 能解決,當然也能檢查答案 NP 完全:NP 裡最難的 目前沒有多項式演算法 SAT、3-SAT 數獨(推廣到 n×n) 排課、地圖三著色 任一個有了快演算法,整個 NP 都有 P = NP 嗎?如果相等,左右兩塊其實是同一塊;絕大多數人相信不相等。 這個問題只問“有沒有多項式演算法”,不問“最快能多快”,後者正是 ETH 要回答的。
圖 1 · NP 裡有容易解決的 P 類,也有最難的 NP 完全問題;SAT 是 NP 完全問題的代表

於是就有了那個著名的問題:P 是否等於 NP?也就是說,凡是答案容易檢查的問題,是不是也都容易解決?這是克雷數學研究所懸賞一百萬美元的七個千禧年難題之一,至今沒有解決。絕大多數研究者相信 P ≠ NP,也就是 SAT 沒有多項式時間演算法。

但“沒有多項式時間演算法”並沒有回答到底要多慢。下面我們就來看,人們為此努力了幾十年,SAT 到底被做到了多快。

三、幾十年的努力:只能改底數

比窮舉快一點

挨個試的方法叫窮舉,要 2n2^n 步。人們找到過不少聰明的辦法。1985 年 Monien 和 Speckenmeyer 發現,可以挑一個子句,按其中的變數分情況討論,很多情況會提前出現矛盾、不必再往下試,這樣做到了約 1.618n1.618^n 步。1999 年 Schöning 的演算法做到了 (4/3)n(4/3)^n3:先隨機給所有變數賦值,哪個子句不滿足,就隨機翻轉它裡面的一個變數,反覆多次。它是一個隨機演算法,允許“拋硬幣”,以極高的機率給出正確答案;與之相對,每一步都確定、同樣的輸入一定得到同樣結果的叫確定性演算法。PPSZ 演算法4經過多年改進,在 2014 年降到 1.308n1.308^n。

換成以 2 為底來比較

這些底數看起來五花八門,換成以 2 為底就能放在一起比。用對數,1.308=2log⁡21.308≈20.3881.308 = 2^{\log_2 1.308} \approx 2^{0.388},所以

1.308n=20.388n1.308^n = 2^{0.388n}

這相當於說:用 PPSZ 解 nn 個變數的問題,和窮舉 0.388n0.388n 個變數一樣難。每一次進步,都只是把指數里 nn 前面的係數往下壓一點,從 1 壓到 0.69,再到 0.42、0.39。

3-SAT 最壞情況演算法的底數 從窮舉的 2 的 n 次方到 2014 年的 1.308 的 n 次方,幾十年的進步都是把底數往下壓,指數里 n 前面的係數始終大於零;2026 年的兩篇論文把這個係數壓到任意小。 每多一個變數,最壞時間乘以幾 條形長度 = log₂(底數),即 2 的多少 n 次方 窮舉所有組合 2ⁿ ≈ 2^1.00n Monien 等 1985 · 確定性 1.618ⁿ ≈ 2^0.69n Schöning 1999 · 隨機 1.334ⁿ ≈ 2^0.42n 確定性紀錄 2018 1.328ⁿ ≈ 2^0.41n PPSZ / Hertli 2014 · 隨機 1.308ⁿ ≈ 2^0.39n 2026 年的兩篇論文 確定性 · 計數 2^δn,δ 可以任意小 前五行的係數都停在 0.38 以上;虛線框表示係數不再有下限,但這隻在 n 大到天文數字時才兌現。
圖 2 · 幾十年的改進都在壓底數,係數從 1 降到約 0.39;新結果說這個係數沒有大於零的下限

時間仍然是“每多一個變數就乘上一個固定倍數”,只是倍數從 2 變成了 1.3。按 1.308 倍算,n=1000n=1000 時步數約 1011710^{117},照樣算不完。這個係數能不能一直壓下去,壓到任意小?還是存在一個大於零的下限?

四、指數時間假說說的是什麼

假說的內容

1999 年,Russell Impagliazzo 和 Ramamohan Paturi 把大家的直覺寫成了一個明確的猜想5,叫指數時間假說(Exponential Time Hypothesis,ETH):

存在一個常數 δ>0\delta>0,使得沒有任何確定性演算法能在 2δn2^{\delta n} 步內解決 nn 個變數的 3-SAT。

用圖 2 的話說:那些條形有一個最短長度 δ\delta,再聰明的演算法也壓不破。它叫“假說”,是因為沒有人能證明它,只是幾十年來所有人都沒能突破,大家傾向於相信它。

它和 P ≠ NP 說的不是一回事。P ≠ NP 只說 3-SAT 沒有多項式時間演算法,比如 n3n^3 步。但在多項式和 2δn2^{\delta n} 之間還有一大片地帶。比如 2n2^{\sqrt n}:n=10000n=10000 時,n3n^3 是 101210^{12},2n=2100≈10302^{\sqrt n}=2^{100}\approx10^{30},而 20.388n2^{0.388n} 有一千多位數。2n2^{\sqrt n} 比任何多項式都慢,又比任何 2δn2^{\delta n} 都快。P ≠ NP 不排除這片地帶裡的演算法,ETH 把它們也排除了。所以 ETH 是比 P ≠ NP 更強的斷言:ETH 成立能推出 P ≠ NP,反過來不行。

2o(n)2^{o(n)} 是什麼意思

新論文說的 2o(n)2^{o(n)},讀作“2 的小 o(n) 次方”。o(n)o(n) 表示一個和 nn 相比越來越微不足道的量,準確說是它除以 nn 的比值隨 nn 增大趨於 0。比如 n\sqrt n:n/n=1/n\sqrt n / n = 1/\sqrt n,n=100n=100 時是 0.1,n=10000n=10000 時是 0.01,越來越小,所以 n\sqrt n 是 o(n)o(n)。而 0.001n0.001n 不是,它除以 nn 永遠是 0.001。

2o(n)2^{o(n)} 的時間叫次指數時間。它的意思是:對任何你給定的 δ>0\delta>0,哪怕是 0.000001,只要 nn 足夠大,它都比 2δn2^{\delta n} 小。所以推翻 ETH 只需要做到:對每一個 δ>0\delta>0,都有一個 2δn2^{\delta n} 步的演算法,也就是圖 2 裡的係數可以壓到任意小。

這和“多項式時間”還差得很遠。上面的 2n2^{\sqrt n} 就是次指數的,照樣算不完。

一串互相牽連的假說

ETH 還有一個更強的兄弟,強指數時間假說(SETH)。允許每個子句有 kk 個變數的問題叫 kk-SAT。SETH 說:kk 越大,kk-SAT 的最好演算法越接近窮舉,係數越接近 1。SETH 成立能推出 ETH 成立。

另一個常用的假設是正交向量假說(OV)。給你兩堆由 0 和 1 組成的等長串,比如 1010 和 0101,要找出一對“沒有同一位都是 1”的串(數學上叫內積為 0、互相正交)。最直接的做法是兩兩比較,每堆 nn 個串就要比 n2n^2 次。OV 說沒有本質上更快的辦法。SETH 能推出 OV。

幾條複雜性假說之間的蘊含關係 SETH 蘊含 ETH,ETH 蘊含 P 不等於 NP,SETH 還蘊含正交向量假說。新結果推翻 ETH,於是 SETH 也被推翻;P 不等於 NP 和正交向量假說不受影響。 從強到弱:箭頭表示“左邊成立,則右邊成立” 蘊含 蘊含 蘊含 SETH 強指數時間假說 k 越大,k-SAT 越接近 2ⁿ 隨 ETH 一起被推翻 ETH 指數時間假說 1999 3-SAT 至少要 2^δn,δ>0 被推翻 P ≠ NP 1971 年提出 3-SAT 沒有多項式演算法 不受影響,仍未解決 OV 正交向量假說 找內積為 0 的一對沒捷徑 不受影響 右邊的被推翻,左邊的跟著倒:ETH 錯了,SETH 也就錯了。 左邊倒了,右邊不受牽連:P ≠ NP 和 OV 都還站著。
圖 3 · 新結果推翻了 ETH,也就連帶推翻了更強的 SETH;更弱的 P ≠ NP 和旁支的 OV 假說不受影響

這些假說之所以重要,是因為大量“下界”結果建立在它們之上。下界是指“某個問題不可能比多快更快”。直接證明下界極難,研究者通常繞一個彎:先證明“如果問題 X 有某種快演算法,那麼把 3-SAT 歸約到 X,3-SAT 就會有次指數演算法”,然後寫下“除非 ETH 不成立,X 就沒有這種快演算法”。Anthropic 的論文裡用 Claude 做了一次文獻檢索,找到 800 多篇論文至少有一個結果只在 ETH 或比它更強的假設下成立1。

並不是所有人都堅信這些假說。2019 年 Ryan Williams 給過一個主觀估計:ETH 為真的可能性約 70%,SETH 約 25%6。

那麼這一次,是誰、用什麼推翻了它,證據有多硬?

五、新聞核實:發生了什麼

時間線

把幾份原始材料對一遍,事情的經過是這樣的:

  • 10 月 16 日,OpenAI 和 Anthropic 的內部模型各自得到了證明。Anthropic 說核心演算法是一個內部研究模型在沒有人類輸入的情況下找到的,用了 1400 萬個輸出 token(模型輸出文字的計數單位,大致一個 token 是一個漢字或半個英文單詞)1。
  • 10 月 17 日,OpenAI 把證明形式化到了 Lean,也就是翻譯成計算機能逐步檢查的形式(下文細說),10 月 25 日修訂論文,26 日公開2。
  • 10 月 26 日,Shiva Kintali 發了一份 22 頁的簡化講解,只用多項式、解方程這類基礎數學,重寫了 OpenAI 證明的主線7。
  • 10 月 27 日,Anthropic 在 Hexagon 預印本平臺發出論文,並公開 Lean 證明8。
  • ETH 的提出者 Impagliazzo、Paturi 和 MIT 的 Ryan Williams 牽頭組成審查組。他們在公開信裡寫明:參與審查不代表認證這個結論。Williams 對 TechCrunch 說,證明裡有些部分看起來很常規,但有“兩三處”非常陌生9。

兩篇論文的結論基本一致:存在確定性演算法,能在大約 2nlog⁡log⁡n/log⁡n2^{n\log\log n/\sqrt{\log n}} 步(再乘上一個常數倍數,這裡 log⁡\log 以 2 為底)內數出 3-SAT 公式有多少組解,對 kk-SAT 也成立。指數里的 log⁡log⁡n/log⁡n\log\log n/\sqrt{\log n} 隨 nn 增大趨於 0,所以這正是 2o(n)2^{o(n)}。數出解的個數比只判斷“有沒有解”更難,比如聚會問題會數出 2;數出來大於零,就說明有解。

Lean 檢查了什麼

Lean 是一種證明助手:把數學證明寫成程式,每一步推理都由一個很小的“核心”程式機械地檢查,核心接受了,就說明從定義到結論沒有邏輯漏洞。Anthropic 的 Lean 證明被三個獨立實現的核心接受,除了 Lean 的三條標準公理(數學裡不加證明、直接承認的出發點)外不依賴任何額外假設,整個證明分成 1050 個檔案1。

但機器只能檢查“從這些定義推出這個結論”。定義本身是不是真的表達了 ETH,機器管不了。Anthropic 在附錄 E 裡寫得很直白:Lean 證明是 AI 寫的,由同一模型的其他例項審閱,寫作時沒有已知的人檢查過。OpenAI 一邊,Lean 裡形式化的執行時間界比論文正文略弱,但仍然是次指數的10。

所以合理的判斷是:兩家用不同的方法獨立得到同一個結論,各自有機器檢查,又有一位人類研究者把其中一份改寫成了可以逐行讀懂的證明,這比通常“某某猜想被推翻”的新聞要可靠得多;但它還沒有經過同行評審(投稿後由同領域專家審稿),審查組也還沒有給出結論。

哪些說法被誇大了

常見說法與原文對照
說法原文怎麼說判斷
AI 推翻了指數時間假說兩篇論文都給出 3-SAT 的確定性次指數演算法,有 Lean 檢查,審查進行中基本屬實
被推翻的只是某個變體推翻的是 ETH 的標準形式,更強的 SETH 隨之一起倒下不對
P = NP 更近了Anthropic 原文:結果不直接涉及 P vs NP不對
NP 難題從此能快速求解只有 n 大於約 10108 時才比窮舉快,原文明確說它對實際求解公式沒有幫助不對
密碼學要變天OpenAI 稱檢查後相當有把握不影響現有密碼系統沒有依據
三十年難題ETH 1999 年提出,到現在 27 年略有誇張

原文出處見文末的 OpenAI、Anthropic 論文和 TechCrunch 報道。

表 3 · 結論本身基本屬實,轉述時附加的推論大多不成立

既然結論大機率成立,真正有意思的問題就來了:幾十年只能改底數,新演算法到底多做了什麼?我們先看老辦法卡在哪裡。

六、分而治之的極限

把公式切成兩半

兩篇論文的演算法都是在數解的個數,我們也從“怎麼數”說起。數解的個數有一個天然的分而治之思路。如果一個公式的變數能分成兩組,每個子句只用到其中一組,那麼兩組各自數出解的個數再相乘就行。比如聚會再多請兩位朋友 D 和 E,他們只受一條“D 和 E 至少來一個”的約束,和 A、B、C 毫無關係,那麼總解數就是“A、B、C 的解數”乘“D、E 的解數”。代價從 2n2^n 降到 2×2n/22 \times 2^{n/2}:n=100n=100 時,從 21002^{100} 降到 2×2502\times2^{50},相當於從 400 億年降到 40 分鐘左右。

實際的公式沒這麼幹淨,總有一些子句橫跨兩組。辦法是把同時連著兩邊的那些變數(叫切口變數)的取值逐一列舉:每固定一種取值,兩半就互不相干,可以分別數完再相乘,最後把所有取值的結果加起來。切口有 cc 個變數,就要列舉 2c2^c 種取值。兩半還可以繼續往下切。

這個辦法好不好用,全看切口有多大。

切口沒法變小

我們做了個小實驗:隨機生成 3-SAT 公式,用一種近似方法找儘量小的均衡切口(切開後兩半的變數數相等)。作為對照,再生成一種“鏈狀”公式,它的每個子句只用三個編號相鄰的變數。結果如下:

均衡切口的大小(啟發式能找到的最小值)
變數數 n鏈狀公式(m = 4n)隨機 3-CNF(m = 2n)隨機公式切口 / n
1002400.40
2002810.41
40021590.40
80023370.42

m 是子句數。指令碼見 /mnt/project-files/eth-research/experiment/e3_separator.py。

表 4 · 鏈狀公式的切口始終是 2,隨機公式的切口始終是 n 的四成左右

對比很鮮明。鏈狀公式的子句只連相鄰的變數,從中間一刀切下去只有 2 個變數跨著兩邊,不管 nn 多大都是 2。隨機公式就不一樣了,切口始終在 0.4n0.4n 左右,不隨 nn 變小。近似方法找到的不一定是最小的,但理論上早就知道這不是方法的問題。把每個變數畫成一個點,在同一個子句裡出現過的變數之間連線,就得到一張圖(這裡的“圖”指點和連線組成的結構)。隨機公式對應的圖是一種擴張圖:從中任取一大塊點,它和外面的連線都很多。所以不管怎麼切成兩個大小相當的部分,跨過去的變數都正比於 nn。

分而治之要列舉切口變數 左邊是鏈狀公式,變數排成一行,從中間切開只有兩個變數同時連著兩半;右邊是隨機公式,切開後大量變數同時連著兩半,這些都要列舉。 鏈狀公式:切口只有 2 個變數 隨機公式:切口隨 n 線性增長 左半 右半 固定強調色的 2 個變數(4 種取值), 兩半就互不相干,可以各數各的再相乘。 實驗:n = 100 … 800,切口恆為 2 強調色的變數都連著兩半,都得列舉。 實驗(m = 2n):切口約 0.4n,不隨 n 變小
圖 4 · 分而治之的代價是 2 的“切口變數數”次方:鏈狀公式切口恆定,隨機公式無論怎麼切都有一大截

切口正比於 nn,列舉它就要 2cn2^{cn}。所以事先固定好怎麼切、再列舉切口的演算法,最多隻能把係數從 1 壓到某個常數,這正是圖 2 裡幾十年的樣子。

切口本身沒法變小,那能不能讓“跨過切口必須對上的資訊”變少?

七、八平方恆等式:用正負相消換掉相等檢驗

把公式畫成圖

Anthropic 的證明先換了一個視角。把每個子句當成圖裡的一個節點,節點有自己的一份變數副本;兩個子句共用變數時連一條邊,邊要檢查兩邊副本的取值相等。一個 0/1 位叫一個位元,一條邊要對上幾個變數,就說它帶幾個位元。解的個數就是“所有副本的所有取值”上,每個節點“子句是否滿足”(1 或 0)和每條邊“兩邊是否相等”(1 或 0)全部乘起來再求和。

切口的代價,就是跨過切口的邊一共帶多少位元。前面的實驗說明,對隨機公式,這個數怎麼切都降不下來。

網格和矩形

演算法先把節點分成若干組,合併成少數幾個大節點,使任意兩個大節點之間都有一條邊,每條邊帶的位元數差不多。然後把這些大節點擺到一個 g×gg\times g 的網格上。擺法是演算法隨便定的,它只用來提供兩種分組:按行分和按列分。

網格上任取兩行兩列,交出四個角:左上 aa、右上 a′a'、左下 bb、右下 b′b'。對角線 aa–b′b' 和 a′a'–bb 這兩條邊既跨行又跨列。設 aa 手裡有一個 3 位元串 xx(三個 0/1 排成一串,比如 101,共 8 種可能)要和 b′b' 手裡的 vv 對上,a′a' 手裡的 yy 要和 bb 手裡的 uu 對上,這兩條邊合起來就是檢驗 [x=v]⋅[y=u][x=v]\cdot[y=u](方括號裡成立記 1,不成立記 0)。

如果把每一行合併成一個大節點,這兩條對角邊都跨在兩行之間,要付 6 位元;按列合併也一樣是 6 位元。行、列兩種合併方式的代價加起來是 12。

一個兩百年前的恆等式

關鍵的一步是下面這個恆等式。它對所有 3 位元串 x,y,u,vx,y,u,v 成立:

2 [x=v] [y=u]=[x⊕y⊕u⊕v=0] (σ(x,y) σ(v,u)+σ(x,u) σ(v,y))2\,[x=v]\,[y=u] = [x\oplus y\oplus u\oplus v = 0]\,\bigl(\sigma(x,y)\,\sigma(v,u) + \sigma(x,u)\,\sigma(v,y)\bigr)

其中 ⊕\oplus 是按位異或:兩個串逐位比較,相同得 0、不同得 1,比如 101 ⊕\oplus 011 = 110。四個串異或為零,就是每一位上四個串的 1 的個數都是偶數。σ\sigma 是一個只取 +1+1 和 −1-1 的函式,論文給出了它的具體寫法(見文末程式碼)。

這個恆等式的來歷很古老。先看一個熟悉的等式:

(a2+b2)(c2+d2)=(ac−bd)2+(ad+bc)2(a^2+b^2)(c^2+d^2) = (ac-bd)^2 + (ad+bc)^2

兩個“兩數平方和”相乘,結果還是兩數平方和,它對應複數的模可以相乘。1818 年 Degen 發現,把“兩個數”換成“八個數”同樣成立,這就是八平方恆等式;1843 年 Graves 重新發現了它,背後是一種由八個實陣列成的“數”,叫八元數11。Anthropic 在附錄 H 裡講了模型怎樣在尋找分解方式的過程中走到這個恆等式,上面的式子就是從它推出來的。Anthropic 在附錄 H 裡講了模型怎樣在搜尋分解方式的過程中走到這個恆等式。

這個式子一共涉及 12 個位元,可以直接驗證。我們把 40964096 種取值全部代進去算了一遍,全部成立。更有意思的是它為什麼成立:

恆等式兩邊逐項比較(x, y, u, v 各 3 位元)
取值左邊 2[x=v][y=u]行選擇項列選擇項組合數
x = v 且 y = u2+1+164
異或為零,但不相等0一個 +1、一個 −1,相消448
異或不為零0003584
兩個具體例子
101, 011, 011, 1012+1+1相等
101, 011, 110, 0000+1−1相消

4096 種取值全部滿足恆等式。指令碼見 /mnt/project-files/eth-research/experiment/e1_eight_square.py。

表 5 · 奇偶約束比相等檢驗寬鬆得多,多放進來的 448 種組合靠正負號兩兩抵消

右邊的方括號只要求四個串異或為零,我們把這個條件叫奇偶約束。滿足它的組合有 512 種,其中真正滿足 x=vx=v、y=uy=u 的只有 64 種。剩下 448 種裡,括號中兩項總是一個 +1+1 一個 −1-1,恰好抵消。原來的“相等檢驗”被換成了一個更寬鬆的奇偶約束,多放進來的組合靠正負號自己消掉。

換了之後省在哪裡

把右邊乘開,得到兩項。論文把含 σ(x,y)σ(v,u)\sigma(x,y)\sigma(v,u) 的叫行選擇,含 σ(x,u)σ(v,y)\sigma(x,u)\sigma(v,y) 的叫列選擇。

一個矩形在恆等式前後的代價 左:矩形四角 a、a′、b、b′ 分別持有 x、y、u、v,兩條對角邊要求 x 等於 v、y 等於 u,按行合併要 6 位元。中:行選擇項只要兩行在 x 異或 y 上一致,3 位元。右:列選擇項按行合併仍要 6 位元,按列合併只要 3 位元。 原來:兩條對角邊 行選擇項 列選擇項 a · x a′ · y b · u b′ · v a–b′ 要求 x = v,a′–b 要求 y = u 合併行 6 位元 · 合併列 6 位元 上一行 x, y 下一行 u, v x⊕y = u⊕v 只對上 3 位元 因子 σ(x,y)·σ(v,u),取 ±1 合併行 3 位元 · 合併列 6 位元 上一行 x, y 下一行 u, v x、y 全部 要對上 6 位元 因子 σ(x,u)·σ(v,y),取 ±1 合併行 6 位元 · 合併列 3 位元 恆等式 2·[x=v]·[y=u] = [x⊕y⊕u⊕v=0]·(σ(x,y)σ(v,u) + σ(x,u)σ(v,y)) 4096 種取值全部成立
圖 5 · 恆等式把一個矩形拆成兩項,每一項都有一個只要 3 位元的合併方向,行、列代價之和從 12 降到 9

看行選擇這一項:按行合併時,上一行手裡有 x,yx,y,下一行手裡有 u,vu,v,奇偶約束其實是 x⊕y=u⊕vx\oplus y = u\oplus v,兩行只需要在“x⊕yx\oplus y”這一個 3 位元串上對上就行。σ(x,y)\sigma(x,y) 只依賴上一行,σ(v,u)\sigma(v,u) 只依賴下一行,各自乘進所在行即可。我們的實驗也驗證了,行選擇項可以寫成“列舉 3 位元 θ\theta,上一行一個函式乘下一行一個函式”的形式。於是按行合併時,行選擇只付 3 位元,列選擇付 6 位元;按列合併時正好反過來。

所以對每一項,挑它便宜的那個方向合併就行。行、列兩種合併的代價之和,從原來的 6+6=126+6=12 降到了 3+6=93+6=9。

代價:項數和一點額外開銷

問題在於,邊上的位元遠不止 3 個。設一條邊帶 3t3t 位元,就把它切成 tt 塊,每塊用一次恆等式,每個矩形就展開成 2t2^t 項,整張網格的項數是 22 的“總位元數的六分之一”次方,又回到指數了。

論文的處理是把項合併:一個矩形裡,按“有幾塊選了列”分組,只有 t+1t+1 組,項數變成多項式級。代價是每組內部還要多記 tt 個位元,標出哪幾塊選了列。這樣行、列兩種合併的代價之和是 11t11t,而原來是 12t12t。兩者中較小的一個不超過 5.5t5.5t,原來是 6t6t。每做一輪,跨在合併後節點之間的位元就乘上了 11/1211/12。

有一點要注意:乘開以後,節點上的值會出現負數,每一項算出來的已經不是“有多少組解”,而是一個帶正負號的和,只有所有項加起來,才回到真正的解數。Austrin、Kaski 和 Kubjas 研究過“按一個固定的順序逐步合併求和”這類演算法,並證明了它們不可能太快12,Anthropic 據此算出,這類演算法的指數至少要有窮舉的 49% 左右。新演算法不受這個限制,因為它把一個和拆成許多帶正負號的和,每個和按不同的方式合併。

一輪只省 1/121/12,怎麼從“省一點”變成“省到任意多”?

八、遞迴:把指數壓到零

一輪合併完,再按位元數重新分組、補齊,得到的正好又是一個“節點數更少、每對節點之間一條邊”的同類問題,只是節點上的值變成了任意整數。於是可以對它再用一次同樣的辦法,這種“對縮小後的同類問題再用同一個辦法”的做法叫遞迴。論文把每一層的係數寫成一個數列的遞推式:

e0=1,eℓ=(1112+2Kℓ−1)eℓ−1+5Kℓ−1e_0 = 1,\qquad e_\ell = \Bigl(\tfrac{11}{12} + \tfrac{2}{K_{\ell-1}}\Bigr)e_{\ell-1} + \tfrac{5}{K_{\ell-1}}

其中 KℓK_\ell 是第 ℓ\ell 層要求的節點數,K0=64K_0 = 64,Kℓ=9Kℓ−116K_\ell = 9K_{\ell-1}^{16}。時間大約是 2eℓm2^{e_\ell m},mm 是子句數。我們按這個遞推式算了 30 層:

每加一層遞迴,指數乘以約 11/12 橫軸是遞迴層數,縱軸是執行時間 2 的 e 乘 m 次方里的係數 e。第 1 層因為節點太少略高於 1,從第 2 層起按 11/12 的比例下降,約第 13 層低於 PPSZ 的 0.39,第 28 層左右低於 0.1。 遞迴層數與指數係數 e(時間約為 2^(e·m)) 0 0.5 1 0 5 10 15 20 25 30 遞迴層數 窮舉 e = 1 PPSZ 1.308ⁿ ≈ 2^0.39n 第 1 層 e≈1.03,K≈10^30 第 2 層 e≈0.94,K≈10^479 第 28 層 e≈0.10 K 是這一層要求的節點數:第 1 層就要約 10^30 個,層數越多要求越是天文數字。
圖 6 · 遞迴的每一層把指數係數乘上約 11/12,層數夠多就能低於任何給定的 δ,代價是對輸入規模的要求爆炸式增長

第 1 層因為 K0=64K_0=64 太小,額外開銷蓋過了節省,係數是 1.03,比窮舉還差。從第 2 層起,係數基本按 11/1211/12 的比例往下走,第 13 層低於 PPSZ 的 0.39,第 28 層低於 0.1。對任何給定的 δ\delta,取足夠多的層數(層數只和 δ\delta 有關,和輸入無關),時間就低於 2δm2^{\delta m}。這裡的時間是按子句數 mm 算的。再用 Impagliazzo、Paturi、Zane 的稀疏化引理13,可以把任意公式拆成若干個子句數不超過變數數固定倍數的公式,於是 2δm2^{\delta m} 也就變成了 2δn2^{\delta n}。這就推翻了 ETH。

但圖裡的 KK 同樣值得看:第 1 層就要求約 103010^{30} 個節點,第 2 層約 1047910^{479} 個。輸入不夠大,這些層根本搭不起來。Anthropic 自己估計:對子句數是變數數 5 倍的公式,要 n>1010000n > 10^{10000} 才比窮舉快;只看 nn 的那個界,要 n>10108n > 10^{10^8}1。這種只在天文規模上才兌現的演算法,圈內叫“銀河演算法”。

即使不管常數,o(n)o(n) 本身也收縮得極慢。兩篇論文的指數是 nlog⁡log⁡n/log⁡nn\log\log n/\sqrt{\log n} 的量級,我們把它除以 nn(把前面省略的常數倍數當成 1,這已經是對演算法很寬容的假設):

次指數的指數除以 n:log₂log₂n / √log₂n
變數數 n比值相當於
10³1.05比窮舉還慢
10⁶0.97和窮舉差不多
10¹²0.84仍不如 PPSZ 的 0.39
10¹⁰⁰0.46
10¹⁰⁰⁰⁰0.08終於明顯低於老演算法

大 O 裡的常數取 1,真實常數更大。指令碼見 /mnt/project-files/eth-research/experiment/e4_numbers.py。

表 6 · 即使不管常數,o(n) 也要到 n 成為天文數字才比老演算法省

到 n=106n=10^6 時這個比值還有 0.97;要到 1010010^{100} 才降到一半。2o(n)2^{o(n)} 在數學上比任何 2δn2^{\delta n} 都快,在現實裡和窮舉沒有區別。

OpenAI 的證明也是這條路嗎?

九、另一條路:變形,再插值

OpenAI 的證明走的是另一條路線。Kintali 的簡化稿把它整理成了只用多項式和解方程的版本7,大意如下。

先把每個子句寫成多項式。比如子句 x1∨¬x2x_1 \lor \lnot x_2 寫成 1−(1−X1)X21-(1-X_1)X_2:只有 X1=0X_1=0、X2=1X_2=1 時它等於 0,其餘三種取值都等於 1,恰好是子句的真假。所有子句的多項式乘起來,滿足全部子句時乘積是 1,否則是 0;對全部取值求和,就是解的個數。

然後對公式做一個變形:把每個變數替換成一個帶引數 TT 的式子,比如把 X3X_3 換成 X3+TX4X_3 + T X_4,T=0T=0 時就是原來的變數。巧妙之處在於,構造好的變形在 T=1,2,…T=1,2,\dots 這些整數點上,每個子句只依賴一小組變數,再加上少量測量值(若干變數的整數加權和)。把測量值列舉一遍,各組就能分開求和再相乘。這時算出來的數可以是負的,不再是解的個數。

最後,把求和結果看成 TT 的多項式 H(T)H(T),它在 T=0T=0 處的值就是解數。我們在 T=1,2,…T=1,2,\dots 這些容易算的點上求出 HH 的值和它的幾階導數,再把整個多項式反推出來,代入 T=0T=0。這一步叫插值,道理和“兩點確定一條直線、三點確定一條拋物線”一樣:一個多項式在足夠多點上的資訊,能唯一確定它本身。

Kintali 給了一個四變數的例子,我們照著算了一遍。公式是 (x1∨x3)∧(x2∨¬x4)(x_1\lor x_3)\land(x_2\lor\lnot x_4),兩個子句各有 3 組滿足,答案是 9。變形取 x3→X3+TX4x_3 \to X_3 + T X_4,x4→X4+TX3x_4 \to X_4 + T X_3,在 T=1T=1 時兩個子句都只依賴 x1x_1、x2x_2 和測量值 y=x3+x4y = x_3 + x_4:

T = 1 時按測量值 y = x₃ + x₄ 分組求和
測量值 y第一組(x₁, x₂)的和第二組中 x₃ + x₄ = y 的個數乘積
0212
1224
2010
從容易算的點回到 T = 0
H(1)2 + 4 + 0 = 6,不是解數
H(1 + z)6 − 4z − z²
代入 z = −16 + 4 − 1 = 9 = 解數

與窮舉結果一致。指令碼見 /mnt/project-files/eth-research/experiment/e2_kintali_toy.py。

表 7 · 在變形後的點上分組求和,得到的不是解數;用插值退回 T = 0 才得到 9

這裡 H(T)=9−2T−T2H(T) = 9 - 2T - T^2,在 T=1T=1 處只有 6。演算法拿不到 HH 的完整表示式,但能在 T=1T=1 附近求出它的展開:令 z=T−1z = T-1,H=9−2(1+z)−(1+z)2=6−4z−z2H = 9 - 2(1+z) - (1+z)^2 = 6 - 4z - z^2。HH 最多是二次的,這三個係數就確定了它,代入 z=−1z=-1(即 T=0T=0)就回到了 9。注意 y=2y=2 那一行,第一組的和是 0,是因為裡面出現了 −1-1 和 +1+1 相消。

要讓這一招在大公式上省時間,引數也是天文數字。簡化稿裡取一個整數 ss,每個測量值的取值範圍是 s2s4s^{2s^4} 量級;s=64s=64 時係數已經降到 0.36,但要求變數數至少約 101.2×10810^{1.2\times10^8},否則直接退回窮舉。

兩條路線細節完全不同,相同的是都放棄了“每一步都在數真實的解”:中間量可以是負數、可以不是整數,靠最後的相消或插值回到正確答案。按老演算法的思路,這樣的步驟不會出現,這大概就是 Williams 說的“陌生”的部分。

十、改變了什麼,沒改變什麼

這次結果的影響範圍
方面是否改變原因
P vs NP沒變次指數仍比任何多項式慢
實際 SAT 求解沒變要 n 大於約 10 的 1 億次方才比窮舉快
現有密碼系統沒變次指數時間不能隨意透過歸約傳遞;OpenAI 稱已檢查
以 ETH、SETH 為前提的下界失去前提800 多篇論文需要逐個檢查,能改掛到 OV 等假設上的保留
圖上的獨立集、團等問題有了新演算法n 個點上 2^δn 步,對任意 δ > 0
電路規模的理論下界有了新結論某類問題無法用線性規模的邏輯電路計算
表 8 · 改變的是理論上的地圖,不是實際的計算

幾點展開說一下。

P vs NP 沒有變。2o(n)2^{o(n)} 仍然比任何多項式慢,兩篇論文都在開頭宣告瞭這一點。

實際的 SAT 求解沒有變。工業界的 SAT 求解器每天在處理上百萬變數的公式,靠的是實際公式裡的結構,和最壞情況的理論界本來就是兩回事。這次的演算法在可想象的規模上都比窮舉慢。

密碼學沒有被攻破。OpenAI 稱檢查過,相當有把握不影響現有密碼系統9。從理論上說,次指數時間也不能隨便透過歸約傳給其他問題:把別的問題改寫成 3-SAT 時,變數數往往會從 nn 變成 n2n^2 甚至更多,2o(n2)2^{o(n^2)} 就不再是次指數了,OpenAI 論文裡專門指出了這一點2。

理論上的影響是實實在在的。建立在 ETH 和 SETH 上的那 800 多篇論文的條件性結論失去了前提,需要逐個檢查能不能改掛到別的假設上,比如沒有被推翻的正交向量假說。另一方面,一批問題直接得到了新演算法:在 nn 個點的圖上挑出一批互不相連的點(獨立集)、挑出一批兩兩相連的點(團)等經典問題,都有了 2δn2^{\delta n} 步的演算法1;數地圖塗色有多少種方案、數兩兩配對有多少種方案,也有了次指數演算法2。藉助 Williams 的“快演算法推出電路下界”定理,還能推出一個關於邏輯電路規模的理論新結論。

做數學的方式在變。這是一個被普遍相信的猜想,由模型在沒有人類輸入的情況下推翻,再由機器檢查。審查組發公開信,一部分就是為了討論 AI 參與研究的規範9。

小結

  1. SAT 是什麼?可滿足性問題:一組用“或”連成的子句,能否找到 0/1 取值讓它們同時成立。3-SAT 是每句最多 3 個變數的版本。檢查答案容易,尋找答案難。
  2. 怎麼比較快慢?看步數隨變數數 nn 怎麼增長。多項式時間算高效,指數時間不算。SAT 是 NP 完全問題,它有多項式演算法當且僅當 P = NP。
  3. 幾十年做到了多快?窮舉要 2n2^n,改進把係數壓到了約 0.39,但始終是指數。
  4. ETH 說什麼?這個係數有一個大於零的下限。它比 P ≠ NP 更強,大量下界結果以它為前提。
  5. 新聞屬實嗎?基本屬實:OpenAI 和 Anthropic 用不同方法獨立證明了 3-SAT 有確定性的次指數(2o(n)2^{o(n)})演算法,ETH 和 SETH 都被推翻,並有 Lean 機器檢查和一份人類簡化稿;但還沒有經過同行評審。它和 P = NP、實用求解、密碼破解都沒有關係。
  6. 老辦法為什麼不行?分而治之要列舉切口變數,隨機公式的切口正比於 nn,所以只能改常數。
  7. 新辦法多做了什麼?用八平方恆等式把一對相等檢驗換成奇偶約束加兩個帶正負號的項,多放進來的組合正負相消;每一項挑便宜的合併方向,跨節點的位元每輪乘以 11/1211/12。
  8. 怎麼壓到零?同樣的辦法遞迴使用,係數按 (11/12)ℓ(11/12)^\ell 下降,層數只依賴目標 δ\delta。代價是每層要求的規模爆炸式增長,要 n>10108n>10^{10^8} 才比窮舉快。
  9. OpenAI 的路線呢?給變數加一個引數做變形,在容易算的點上求值,再插值回原問題。兩條路的共同點是允許中間量為負、靠相消回到答案。

第七節的恆等式最容易親手驗證。下面這段 Python 按 Anthropic 論文第 2.4 節給出的 σ\sigma,把 4096 種取值全部代進去:

Python
from itertools import product
B3 = list(product((0, 1), repeat=3))
def sigma(p, q): # 论文 2.4 节的 σ,取 ±1
s = sum(p[k] * q[j] for k in range(3) for j in range(k, 3))
s += q[0]*p[1]*p[2] + p[0]*q[1]*p[2] + p[0]*p[1]*q[2]
return -1 if s % 2 else 1
def xor(*vs):
return tuple(sum(b) % 2 for b in zip(*vs))
ok = sum(
2 * (x == v) * (y == u)
== (xor(x, y, u, v) == (0, 0, 0)) * (sigma(x, y) * sigma(v, u) + sigma(x, u) * sigma(v, y))
for x, y, u, v in product(B3, repeat=4)
)
print(ok) # 4096

參考資料

參考資料

  1. A 2^o(n) Time Algorithm for 3-SATClaude (Anthropic) · Hexagon 預印本 2610.00577v1 · 2026-10-27hexagonmath.org ↗核心演算法 10 月 16 日由內部研究模型在無人類輸入下找到,用了 1400 萬輸出 token。第 1 節給出“只有 n 大於 10^(10^8) 才比窮舉快”的估計,附錄 E 說明 Lean 裡檢查了什麼、沒檢查什麼。https://hexagonmath.org/2610.00577v1 ↩ ↩2 ↩3 ↩4 ↩5 ↩6

  2. The Exponential Time Hypothesis is FalseOpenAI · GitHub · openai/math · 2026-10-25github.com ↗手稿 10 月 17 日,修訂 10 月 25 日,10 月 26 日公開。主定理:對每個固定 k,確定性地在 2^O(n·loglog n/√log n) 時間、多項式空間內精確計數 k-CNF 的解。https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf ↩ ↩2 ↩3 ↩4

  3. A Probabilistic Algorithm for k-SAT and Constraint Satisfaction ProblemsUwe Schöning · FOCS 1999 · 1999doi.org ↗https://doi.org/10.1109/SFFCS.1999.814612 ↩

  4. An Improved Exponential-Time Algorithm for k-SATRamamohan Paturi, Pavel Pudlák, Michael Saks, Francis Zane · Journal of the ACM 52(3) · 2005doi.org ↗https://doi.org/10.1145/1066100.1066101 ↩

  5. On the Complexity of k-SATRussell Impagliazzo, Ramamohan Paturi · Journal of Computer and System Sciences 62(2) · 2001doi.org ↗ETH 和 SETH 的出處,會議版 CCC 1999。https://doi.org/10.1006/jcss.2000.1727 ↩

  6. Some Estimated Likelihoods for Computational ComplexityR. Ryan Williams · Computing and Software Science, LNCS 10000 · 2019doi.org ↗主觀估計 ETH 為真約 70%,SETH 為真約 25%。https://doi.org/10.1007/978-3-319-91908-9_2 ↩

  7. A simplified proof of ETH is falseShiva Kintali · 2026-10-26shivakintali.github.io ↗對 OpenAI 證明主線的 22 頁簡化講解,只用稀疏化引理、線性代數和插值;第 2.4 節是本文復現的四變數例子。https://shivakintali.github.io/papers/ETH.pdf ↩ ↩2

  8. anthropics/formal-math: ethAnthropic · GitHub · 2026-10-27github.com ↗Lean 4 形式化,入口是 MainResults.lean。https://github.com/anthropics/formal-math/tree/main/eth ↩

  9. Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?TechCrunch · 2026-10-27techcrunch.com ↗Ryan Williams 的評價(“兩三處很陌生”)、審查組與公開信、OpenAI 對密碼學影響的說法。https://techcrunch.com/2026/10/27/frontier-ai-labs-say-their-models-refuted-the-exponential-time-hypothesis-what-does-that-mean/ ↩ ↩2 ↩3

  10. The Exponential Time Hypothesis is FalseJohn D. Cook · 2026-10-27johndcook.com ↗彙總三份證明連結;評論區提到 Lean 裡形式化的界比論文略弱。https://www.johndcook.com/blog/2026/10/27/eth-false/ ↩

  11. The OctonionsJohn C. Baez · Bulletin of the AMS 39(2) · 2002arxiv.org ↗第 1 節講 Degen 1818 年、Graves 1843 年的八平方恆等式與八元數。https://arxiv.org/abs/math/0105155 ↩

  12. Tensor Network Complexity of Multilinear MapsPer Austrin, Petteri Kaski, Kaie Kubjas · Theory of Computing 18(16) · 2022arxiv.org ↗按一棵收縮樹計算這類求和的模型裡的下界;Anthropic 論文附錄 G 據此算出該模型下指數至少約為窮舉的 49%。https://arxiv.org/abs/1712.09630 ↩

  13. Which Problems Have Strongly Exponential Complexity?Russell Impagliazzo, Ramamohan Paturi, Francis Zane · Journal of Computer and System Sciences 63(4) · 2001doi.org ↗稀疏化引理:任意 3-CNF 可以寫成 2^(εn) 個子句數線性的公式之“或”。https://doi.org/10.1006/jcss.2001.1774 ↩