We refute the Exponential Time Hypothesis (ETH) by presenting a deterministic algorithm for 3-SAT on n variables that runs in time.
這是 2026 年 10 月 27 日公開的一篇預印本(還沒經過期刊審稿、先放到網上的論文)摘要的第一句,作者一欄寫的是 Claude1。翻譯過來是:“我們給出一個在 時間內解決 個變數的 3-SAT 的確定性演算法,從而推翻了指數時間假說(ETH)。”前一天,OpenAI 也在 GitHub 上放出了一篇標題直接叫《指數時間假說是錯的》的論文2。轉到中文社交媒體上,標題很快變成了“AI 推翻三十年計算機難題”“P=NP 又近了一步”“密碼學要變天”。
這句話裡幾乎每個詞都需要解釋:3-SAT 是什麼?“指數時間”指什麼,憑什麼是一個“假說”? 是快還是慢?它和大名鼎鼎的 P vs NP 又是什麼關係?兩家 AI 是怎麼做到的,結論靠得住嗎?
這些問題都可以從一道簡單的邏輯題講起。
一、一道邏輯謎題:什麼是 SAT
安排一次聚會
假設你要請三位朋友 A、B、C 來家裡,但他們之間有些講究:
- A 和 B 至少要來一個,不然沒人張羅。
- A 和 C 不能都來,他們倆合不來。
- 如果 B 來,C 也得來,B 一個人不肯來。
- A 和 C 至少要來一個,因為只有他們會做飯。
有沒有一種邀請方案,讓四條要求同時滿足?
每位朋友只有“來”和“不來”兩種狀態。我們用一個變數表示,來記作 1,不來記作 0。這種只能取 0 和 1(也可以說“真”和“假”)兩個值的變數叫布林變數,名字來自 19 世紀的數學家布林(George Boole),他最早把邏輯寫成了代數。下面用小寫的 分別表示 A、B、C 來不來。
再看每條要求。第 1 條是“A 來,或者 B 來”,寫成 ,符號 讀作“或”,兩邊只要有一個成立,整句就成立。第 2 條“A 和 C 不能都來”換個說法是“A 不來,或者 C 不來”。“不來”是“來”的反面,用 表示,讀作“非 ”, 時 ,反之亦然。於是第 2 條寫成 。第 3 條“如果 B 來,C 也得來”,等價於“B 不來,或者 C 來”,寫成 。第 4 條是 。
像 這樣,幾個變數(或它們的反面)用“或”連起來的一句話,叫一個子句。四條要求必須同時成立,用“且”()把它們連起來:
“一串子句用‘且’連起來”的這種寫法叫合取正規化(CNF,合取就是“且”的意思)。現在問題可以說得很精確了:給定一個合取正規化,有沒有一組 0/1 取值,讓它整體成立?這個問題叫可滿足性問題,英文 Boolean Satisfiability,縮寫就是 SAT。如果每個子句最多隻有 3 個變數,就叫 3-SAT。我們的聚會問題每句只有 2 個變數,當然也算 3-SAT 的一個例子。
最笨的辦法:挨個試
三個人,每人兩種狀態,一共 種方案。全部列出來檢查一遍:
| a | b | c | 哪條要求沒滿足 | 結果 |
|---|---|---|---|---|
| 0 | 0 | 0 | 第 1 條(A、B 都沒來) | 不行 |
| 0 | 0 | 1 | 第 1 條 | 不行 |
| 0 | 1 | 0 | 第 3 條(B 來了 C 沒來) | 不行 |
| 0 | 1 | 1 | 都滿足 | 可以 |
| 1 | 0 | 0 | 都滿足 | 可以 |
| 1 | 0 | 1 | 第 2 條(A、C 都來了) | 不行 |
| 1 | 1 | 0 | 第 3 條 | 不行 |
| 1 | 1 | 1 | 第 2 條 | 不行 |
檢查一個方案只要看四條要求;找出可行方案,這裡靠的是把 8 種都試一遍。
答案是有兩種方案:只請 A,或者請 B 和 C。
這張表也顯示出 SAT 的一個特點。拿到一個方案,檢查它對不對很容易,四條要求逐條看一遍就行;但要找到一個對的方案,最直接的辦法只有挨個試。
人數一多,挨個試就不行了。每多一個變數,方案數就翻一倍, 個變數就有 種。 時大約是 種,一臺每秒檢查一萬億()種的計算機要算 19 分鐘; 時約 種,要算 400 億年,是宇宙年齡的三倍。實際中的 SAT 問題常有幾千、幾萬個變數。
為什麼要關心這樣一道謎題?因為大量現實問題都能寫成 SAT。排課(某老師週一上午不能有課,兩門課不能同時在一間教室)、檢查晶片設計有沒有錯、填數獨,都可以把“選或不選”“是或不是”設成布林變數,把規則寫成子句。SAT 會解了,這些問題就都會解了。
那麼,除了挨個試,到底有沒有本質上更快的辦法?要討論“更快”,得先說清楚怎麼比較快慢。
二、演算法的快與慢
數步數,而不是看秒錶
同一個演算法,在新電腦上跑得快,在舊電腦上跑得慢,所以電腦科學不用秒錶衡量演算法,而是看步數怎樣隨問題規模增長。問題規模記作 ,對 SAT 來說就是變數個數。
有的演算法的步數是 、 這樣的冪函式,或者幾個冪函式相加,這叫多項式時間;有的是 這樣的指數函式,叫指數時間。這兩類函式在 小的時候看不出差別, 一大差距就大得離譜:
| n | n² | n³ | 2ⁿ |
|---|---|---|---|
| 10 | 100 | 1,000 | 1,024 |
| 20 | 400 | 8,000 | 約 100 萬 |
| 50 | 2,500 | 125,000 | 約 10¹⁵ |
| 100 | 10,000 | 1,000,000 | 約 1.3 × 10³⁰ |
| 每秒 10¹² 步的計算機,n = 100 時要算 | |||
| 用時 | 不到 1 微秒 | 1 微秒 | 約 400 億年 |
多項式時間的演算法, 翻一倍, 也只是變成原來的 8 倍,電腦快一點就追得上。指數時間的演算法, 只要加 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?也就是說,凡是答案容易檢查的問題,是不是也都容易解決?這是克雷數學研究所懸賞一百萬美元的七個千禧年難題之一,至今沒有解決。絕大多數研究者相信 P ≠ NP,也就是 SAT 沒有多項式時間演算法。
但“沒有多項式時間演算法”並沒有回答到底要多慢。下面我們就來看,人們為此努力了幾十年,SAT 到底被做到了多快。
三、幾十年的努力:只能改底數
比窮舉快一點
挨個試的方法叫窮舉,要 步。人們找到過不少聰明的辦法。1985 年 Monien 和 Speckenmeyer 發現,可以挑一個子句,按其中的變數分情況討論,很多情況會提前出現矛盾、不必再往下試,這樣做到了約 步。1999 年 Schöning 的演算法做到了 3:先隨機給所有變數賦值,哪個子句不滿足,就隨機翻轉它裡面的一個變數,反覆多次。它是一個隨機演算法,允許“拋硬幣”,以極高的機率給出正確答案;與之相對,每一步都確定、同樣的輸入一定得到同樣結果的叫確定性演算法。PPSZ 演算法4經過多年改進,在 2014 年降到 。
換成以 2 為底來比較
這些底數看起來五花八門,換成以 2 為底就能放在一起比。用對數,,所以
這相當於說:用 PPSZ 解 個變數的問題,和窮舉 個變數一樣難。每一次進步,都只是把指數里 前面的係數往下壓一點,從 1 壓到 0.69,再到 0.42、0.39。
時間仍然是“每多一個變數就乘上一個固定倍數”,只是倍數從 2 變成了 1.3。按 1.308 倍算, 時步數約 ,照樣算不完。這個係數能不能一直壓下去,壓到任意小?還是存在一個大於零的下限?
四、指數時間假說說的是什麼
假說的內容
1999 年,Russell Impagliazzo 和 Ramamohan Paturi 把大家的直覺寫成了一個明確的猜想5,叫指數時間假說(Exponential Time Hypothesis,ETH):
存在一個常數 ,使得沒有任何確定性演算法能在 步內解決 個變數的 3-SAT。
用圖 2 的話說:那些條形有一個最短長度 ,再聰明的演算法也壓不破。它叫“假說”,是因為沒有人能證明它,只是幾十年來所有人都沒能突破,大家傾向於相信它。
它和 P ≠ NP 說的不是一回事。P ≠ NP 只說 3-SAT 沒有多項式時間演算法,比如 步。但在多項式和 之間還有一大片地帶。比如 : 時, 是 ,,而 有一千多位數。 比任何多項式都慢,又比任何 都快。P ≠ NP 不排除這片地帶裡的演算法,ETH 把它們也排除了。所以 ETH 是比 P ≠ NP 更強的斷言:ETH 成立能推出 P ≠ NP,反過來不行。
是什麼意思
新論文說的 ,讀作“2 的小 o(n) 次方”。 表示一個和 相比越來越微不足道的量,準確說是它除以 的比值隨 增大趨於 0。比如 :, 時是 0.1, 時是 0.01,越來越小,所以 是 。而 不是,它除以 永遠是 0.001。
的時間叫次指數時間。它的意思是:對任何你給定的 ,哪怕是 0.000001,只要 足夠大,它都比 小。所以推翻 ETH 只需要做到:對每一個 ,都有一個 步的演算法,也就是圖 2 裡的係數可以壓到任意小。
這和“多項式時間”還差得很遠。上面的 就是次指數的,照樣算不完。
一串互相牽連的假說
ETH 還有一個更強的兄弟,強指數時間假說(SETH)。允許每個子句有 個變數的問題叫 -SAT。SETH 說: 越大,-SAT 的最好演算法越接近窮舉,係數越接近 1。SETH 成立能推出 ETH 成立。
另一個常用的假設是正交向量假說(OV)。給你兩堆由 0 和 1 組成的等長串,比如 1010 和 0101,要找出一對“沒有同一位都是 1”的串(數學上叫內積為 0、互相正交)。最直接的做法是兩兩比較,每堆 個串就要比 次。OV 說沒有本質上更快的辦法。SETH 能推出 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。
兩篇論文的結論基本一致:存在確定性演算法,能在大約 步(再乘上一個常數倍數,這裡 以 2 為底)內數出 3-SAT 公式有多少組解,對 -SAT 也成立。指數里的 隨 增大趨於 0,所以這正是 。數出解的個數比只判斷“有沒有解”更難,比如聚會問題會數出 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 報道。
既然結論大機率成立,真正有意思的問題就來了:幾十年只能改底數,新演算法到底多做了什麼?我們先看老辦法卡在哪裡。
六、分而治之的極限
把公式切成兩半
兩篇論文的演算法都是在數解的個數,我們也從“怎麼數”說起。數解的個數有一個天然的分而治之思路。如果一個公式的變數能分成兩組,每個子句只用到其中一組,那麼兩組各自數出解的個數再相乘就行。比如聚會再多請兩位朋友 D 和 E,他們只受一條“D 和 E 至少來一個”的約束,和 A、B、C 毫無關係,那麼總解數就是“A、B、C 的解數”乘“D、E 的解數”。代價從 降到 : 時,從 降到 ,相當於從 400 億年降到 40 分鐘左右。
實際的公式沒這麼幹淨,總有一些子句橫跨兩組。辦法是把同時連著兩邊的那些變數(叫切口變數)的取值逐一列舉:每固定一種取值,兩半就互不相干,可以分別數完再相乘,最後把所有取值的結果加起來。切口有 個變數,就要列舉 種取值。兩半還可以繼續往下切。
這個辦法好不好用,全看切口有多大。
切口沒法變小
我們做了個小實驗:隨機生成 3-SAT 公式,用一種近似方法找儘量小的均衡切口(切開後兩半的變數數相等)。作為對照,再生成一種“鏈狀”公式,它的每個子句只用三個編號相鄰的變數。結果如下:
| 變數數 n | 鏈狀公式(m = 4n) | 隨機 3-CNF(m = 2n) | 隨機公式切口 / n |
|---|---|---|---|
| 100 | 2 | 40 | 0.40 |
| 200 | 2 | 81 | 0.41 |
| 400 | 2 | 159 | 0.40 |
| 800 | 2 | 337 | 0.42 |
m 是子句數。指令碼見 /mnt/project-files/eth-research/experiment/e3_separator.py。
對比很鮮明。鏈狀公式的子句只連相鄰的變數,從中間一刀切下去只有 2 個變數跨著兩邊,不管 多大都是 2。隨機公式就不一樣了,切口始終在 左右,不隨 變小。近似方法找到的不一定是最小的,但理論上早就知道這不是方法的問題。把每個變數畫成一個點,在同一個子句裡出現過的變數之間連線,就得到一張圖(這裡的“圖”指點和連線組成的結構)。隨機公式對應的圖是一種擴張圖:從中任取一大塊點,它和外面的連線都很多。所以不管怎麼切成兩個大小相當的部分,跨過去的變數都正比於 。
切口正比於 ,列舉它就要 。所以事先固定好怎麼切、再列舉切口的演算法,最多隻能把係數從 1 壓到某個常數,這正是圖 2 裡幾十年的樣子。
切口本身沒法變小,那能不能讓“跨過切口必須對上的資訊”變少?
七、八平方恆等式:用正負相消換掉相等檢驗
把公式畫成圖
Anthropic 的證明先換了一個視角。把每個子句當成圖裡的一個節點,節點有自己的一份變數副本;兩個子句共用變數時連一條邊,邊要檢查兩邊副本的取值相等。一個 0/1 位叫一個位元,一條邊要對上幾個變數,就說它帶幾個位元。解的個數就是“所有副本的所有取值”上,每個節點“子句是否滿足”(1 或 0)和每條邊“兩邊是否相等”(1 或 0)全部乘起來再求和。
切口的代價,就是跨過切口的邊一共帶多少位元。前面的實驗說明,對隨機公式,這個數怎麼切都降不下來。
網格和矩形
演算法先把節點分成若干組,合併成少數幾個大節點,使任意兩個大節點之間都有一條邊,每條邊帶的位元數差不多。然後把這些大節點擺到一個 的網格上。擺法是演算法隨便定的,它只用來提供兩種分組:按行分和按列分。
網格上任取兩行兩列,交出四個角:左上 、右上 、左下 、右下 。對角線 – 和 – 這兩條邊既跨行又跨列。設 手裡有一個 3 位元串 (三個 0/1 排成一串,比如 101,共 8 種可能)要和 手裡的 對上, 手裡的 要和 手裡的 對上,這兩條邊合起來就是檢驗 (方括號裡成立記 1,不成立記 0)。
如果把每一行合併成一個大節點,這兩條對角邊都跨在兩行之間,要付 6 位元;按列合併也一樣是 6 位元。行、列兩種合併方式的代價加起來是 12。
一個兩百年前的恆等式
關鍵的一步是下面這個恆等式。它對所有 3 位元串 成立:
其中 是按位異或:兩個串逐位比較,相同得 0、不同得 1,比如 101 011 = 110。四個串異或為零,就是每一位上四個串的 1 的個數都是偶數。 是一個只取 和 的函式,論文給出了它的具體寫法(見文末程式碼)。
這個恆等式的來歷很古老。先看一個熟悉的等式:
兩個“兩數平方和”相乘,結果還是兩數平方和,它對應複數的模可以相乘。1818 年 Degen 發現,把“兩個數”換成“八個數”同樣成立,這就是八平方恆等式;1843 年 Graves 重新發現了它,背後是一種由八個實陣列成的“數”,叫八元數11。Anthropic 在附錄 H 裡講了模型怎樣在尋找分解方式的過程中走到這個恆等式,上面的式子就是從它推出來的。Anthropic 在附錄 H 裡講了模型怎樣在搜尋分解方式的過程中走到這個恆等式。
這個式子一共涉及 12 個位元,可以直接驗證。我們把 種取值全部代進去算了一遍,全部成立。更有意思的是它為什麼成立:
| 取值 | 左邊 2[x=v][y=u] | 行選擇項 | 列選擇項 | 組合數 |
|---|---|---|---|---|
| x = v 且 y = u | 2 | +1 | +1 | 64 |
| 異或為零,但不相等 | 0 | 一個 +1、一個 −1,相消 | 448 | |
| 異或不為零 | 0 | 0 | 0 | 3584 |
| 兩個具體例子 | ||||
| 101, 011, 011, 101 | 2 | +1 | +1 | 相等 |
| 101, 011, 110, 000 | 0 | +1 | −1 | 相消 |
4096 種取值全部滿足恆等式。指令碼見 /mnt/project-files/eth-research/experiment/e1_eight_square.py。
右邊的方括號只要求四個串異或為零,我們把這個條件叫奇偶約束。滿足它的組合有 512 種,其中真正滿足 、 的只有 64 種。剩下 448 種裡,括號中兩項總是一個 一個 ,恰好抵消。原來的“相等檢驗”被換成了一個更寬鬆的奇偶約束,多放進來的組合靠正負號自己消掉。
換了之後省在哪裡
把右邊乘開,得到兩項。論文把含 的叫行選擇,含 的叫列選擇。
看行選擇這一項:按行合併時,上一行手裡有 ,下一行手裡有 ,奇偶約束其實是 ,兩行只需要在“”這一個 3 位元串上對上就行。 只依賴上一行, 只依賴下一行,各自乘進所在行即可。我們的實驗也驗證了,行選擇項可以寫成“列舉 3 位元 ,上一行一個函式乘下一行一個函式”的形式。於是按行合併時,行選擇只付 3 位元,列選擇付 6 位元;按列合併時正好反過來。
所以對每一項,挑它便宜的那個方向合併就行。行、列兩種合併的代價之和,從原來的 降到了 。
代價:項數和一點額外開銷
問題在於,邊上的位元遠不止 3 個。設一條邊帶 位元,就把它切成 塊,每塊用一次恆等式,每個矩形就展開成 項,整張網格的項數是 的“總位元數的六分之一”次方,又回到指數了。
論文的處理是把項合併:一個矩形裡,按“有幾塊選了列”分組,只有 組,項數變成多項式級。代價是每組內部還要多記 個位元,標出哪幾塊選了列。這樣行、列兩種合併的代價之和是 ,而原來是 。兩者中較小的一個不超過 ,原來是 。每做一輪,跨在合併後節點之間的位元就乘上了 。
有一點要注意:乘開以後,節點上的值會出現負數,每一項算出來的已經不是“有多少組解”,而是一個帶正負號的和,只有所有項加起來,才回到真正的解數。Austrin、Kaski 和 Kubjas 研究過“按一個固定的順序逐步合併求和”這類演算法,並證明了它們不可能太快12,Anthropic 據此算出,這類演算法的指數至少要有窮舉的 49% 左右。新演算法不受這個限制,因為它把一個和拆成許多帶正負號的和,每個和按不同的方式合併。
一輪只省 ,怎麼從“省一點”變成“省到任意多”?
八、遞迴:把指數壓到零
一輪合併完,再按位元數重新分組、補齊,得到的正好又是一個“節點數更少、每對節點之間一條邊”的同類問題,只是節點上的值變成了任意整數。於是可以對它再用一次同樣的辦法,這種“對縮小後的同類問題再用同一個辦法”的做法叫遞迴。論文把每一層的係數寫成一個數列的遞推式:
其中 是第 層要求的節點數,,。時間大約是 , 是子句數。我們按這個遞推式算了 30 層:
第 1 層因為 太小,額外開銷蓋過了節省,係數是 1.03,比窮舉還差。從第 2 層起,係數基本按 的比例往下走,第 13 層低於 PPSZ 的 0.39,第 28 層低於 0.1。對任何給定的 ,取足夠多的層數(層數只和 有關,和輸入無關),時間就低於 。這裡的時間是按子句數 算的。再用 Impagliazzo、Paturi、Zane 的稀疏化引理13,可以把任意公式拆成若干個子句數不超過變數數固定倍數的公式,於是 也就變成了 。這就推翻了 ETH。
但圖裡的 同樣值得看:第 1 層就要求約 個節點,第 2 層約 個。輸入不夠大,這些層根本搭不起來。Anthropic 自己估計:對子句數是變數數 5 倍的公式,要 才比窮舉快;只看 的那個界,要 1。這種只在天文規模上才兌現的演算法,圈內叫“銀河演算法”。
即使不管常數, 本身也收縮得極慢。兩篇論文的指數是 的量級,我們把它除以 (把前面省略的常數倍數當成 1,這已經是對演算法很寬容的假設):
| 變數數 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。
到 時這個比值還有 0.97;要到 才降到一半。 在數學上比任何 都快,在現實裡和窮舉沒有區別。
OpenAI 的證明也是這條路嗎?
九、另一條路:變形,再插值
OpenAI 的證明走的是另一條路線。Kintali 的簡化稿把它整理成了只用多項式和解方程的版本7,大意如下。
先把每個子句寫成多項式。比如子句 寫成 :只有 、 時它等於 0,其餘三種取值都等於 1,恰好是子句的真假。所有子句的多項式乘起來,滿足全部子句時乘積是 1,否則是 0;對全部取值求和,就是解的個數。
然後對公式做一個變形:把每個變數替換成一個帶引數 的式子,比如把 換成 , 時就是原來的變數。巧妙之處在於,構造好的變形在 這些整數點上,每個子句只依賴一小組變數,再加上少量測量值(若干變數的整數加權和)。把測量值列舉一遍,各組就能分開求和再相乘。這時算出來的數可以是負的,不再是解的個數。
最後,把求和結果看成 的多項式 ,它在 處的值就是解數。我們在 這些容易算的點上求出 的值和它的幾階導數,再把整個多項式反推出來,代入 。這一步叫插值,道理和“兩點確定一條直線、三點確定一條拋物線”一樣:一個多項式在足夠多點上的資訊,能唯一確定它本身。
Kintali 給了一個四變數的例子,我們照著算了一遍。公式是 ,兩個子句各有 3 組滿足,答案是 9。變形取 ,,在 時兩個子句都只依賴 、 和測量值 :
| 測量值 y | 第一組(x₁, x₂)的和 | 第二組中 x₃ + x₄ = y 的個數 | 乘積 |
|---|---|---|---|
| 0 | 2 | 1 | 2 |
| 1 | 2 | 2 | 4 |
| 2 | 0 | 1 | 0 |
| 從容易算的點回到 T = 0 | |||
| H(1) | 2 + 4 + 0 = 6,不是解數 | ||
| H(1 + z) | 6 − 4z − z² | ||
| 代入 z = −1 | 6 + 4 − 1 = 9 = 解數 | ||
與窮舉結果一致。指令碼見 /mnt/project-files/eth-research/experiment/e2_kintali_toy.py。
這裡 ,在 處只有 6。演算法拿不到 的完整表示式,但能在 附近求出它的展開:令 ,。 最多是二次的,這三個係數就確定了它,代入 (即 )就回到了 9。注意 那一行,第一組的和是 0,是因為裡面出現了 和 相消。
要讓這一招在大公式上省時間,引數也是天文數字。簡化稿裡取一個整數 ,每個測量值的取值範圍是 量級; 時係數已經降到 0.36,但要求變數數至少約 ,否則直接退回窮舉。
兩條路線細節完全不同,相同的是都放棄了“每一步都在數真實的解”:中間量可以是負數、可以不是整數,靠最後的相消或插值回到正確答案。按老演算法的思路,這樣的步驟不會出現,這大概就是 Williams 說的“陌生”的部分。
十、改變了什麼,沒改變什麼
| 方面 | 是否改變 | 原因 |
|---|---|---|
| P vs NP | 沒變 | 次指數仍比任何多項式慢 |
| 實際 SAT 求解 | 沒變 | 要 n 大於約 10 的 1 億次方才比窮舉快 |
| 現有密碼系統 | 沒變 | 次指數時間不能隨意透過歸約傳遞;OpenAI 稱已檢查 |
| 以 ETH、SETH 為前提的下界 | 失去前提 | 800 多篇論文需要逐個檢查,能改掛到 OV 等假設上的保留 |
| 圖上的獨立集、團等問題 | 有了新演算法 | n 個點上 2^δn 步,對任意 δ > 0 |
| 電路規模的理論下界 | 有了新結論 | 某類問題無法用線性規模的邏輯電路計算 |
幾點展開說一下。
P vs NP 沒有變。 仍然比任何多項式慢,兩篇論文都在開頭宣告瞭這一點。
實際的 SAT 求解沒有變。工業界的 SAT 求解器每天在處理上百萬變數的公式,靠的是實際公式裡的結構,和最壞情況的理論界本來就是兩回事。這次的演算法在可想象的規模上都比窮舉慢。
密碼學沒有被攻破。OpenAI 稱檢查過,相當有把握不影響現有密碼系統9。從理論上說,次指數時間也不能隨便透過歸約傳給其他問題:把別的問題改寫成 3-SAT 時,變數數往往會從 變成 甚至更多, 就不再是次指數了,OpenAI 論文裡專門指出了這一點2。
理論上的影響是實實在在的。建立在 ETH 和 SETH 上的那 800 多篇論文的條件性結論失去了前提,需要逐個檢查能不能改掛到別的假設上,比如沒有被推翻的正交向量假說。另一方面,一批問題直接得到了新演算法:在 個點的圖上挑出一批互不相連的點(獨立集)、挑出一批兩兩相連的點(團)等經典問題,都有了 步的演算法1;數地圖塗色有多少種方案、數兩兩配對有多少種方案,也有了次指數演算法2。藉助 Williams 的“快演算法推出電路下界”定理,還能推出一個關於邏輯電路規模的理論新結論。
做數學的方式在變。這是一個被普遍相信的猜想,由模型在沒有人類輸入的情況下推翻,再由機器檢查。審查組發公開信,一部分就是為了討論 AI 參與研究的規範9。
小結
- SAT 是什麼?可滿足性問題:一組用“或”連成的子句,能否找到 0/1 取值讓它們同時成立。3-SAT 是每句最多 3 個變數的版本。檢查答案容易,尋找答案難。
- 怎麼比較快慢?看步數隨變數數 怎麼增長。多項式時間算高效,指數時間不算。SAT 是 NP 完全問題,它有多項式演算法當且僅當 P = NP。
- 幾十年做到了多快?窮舉要 ,改進把係數壓到了約 0.39,但始終是指數。
- ETH 說什麼?這個係數有一個大於零的下限。它比 P ≠ NP 更強,大量下界結果以它為前提。
- 新聞屬實嗎?基本屬實:OpenAI 和 Anthropic 用不同方法獨立證明了 3-SAT 有確定性的次指數()演算法,ETH 和 SETH 都被推翻,並有 Lean 機器檢查和一份人類簡化稿;但還沒有經過同行評審。它和 P = NP、實用求解、密碼破解都沒有關係。
- 老辦法為什麼不行?分而治之要列舉切口變數,隨機公式的切口正比於 ,所以只能改常數。
- 新辦法多做了什麼?用八平方恆等式把一對相等檢驗換成奇偶約束加兩個帶正負號的項,多放進來的組合正負相消;每一項挑便宜的合併方向,跨節點的位元每輪乘以 。
- 怎麼壓到零?同樣的辦法遞迴使用,係數按 下降,層數只依賴目標 。代價是每層要求的規模爆炸式增長,要 才比窮舉快。
- OpenAI 的路線呢?給變數加一個引數做變形,在容易算的點上求值,再插值回原問題。兩條路的共同點是允許中間量為負、靠相消回到答案。
第七節的恆等式最容易親手驗證。下面這段 Python 按 Anthropic 論文第 2.4 節給出的 ,把 4096 種取值全部代進去:
from itertools import productB3 = 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參考資料
參考資料
-
A 2^o(n) Time Algorithm for 3-SAThexagonmath.org ↗核心演算法 10 月 16 日由內部研究模型在無人類輸入下找到,用了 1400 萬輸出 token。第 1 節給出“只有 n 大於 10^(10^8) 才比窮舉快”的估計,附錄 E 說明 Lean 裡檢查了什麼、沒檢查什麼。https://hexagonmath.org/2610.00577v1 ↩ ↩2 ↩3 ↩4 ↩5 ↩6
-
The Exponential Time Hypothesis is Falsegithub.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
-
A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problemsdoi.org ↗https://doi.org/10.1109/SFFCS.1999.814612 ↩
-
An Improved Exponential-Time Algorithm for k-SATdoi.org ↗https://doi.org/10.1145/1066100.1066101 ↩
-
On the Complexity of k-SATdoi.org ↗ETH 和 SETH 的出處,會議版 CCC 1999。https://doi.org/10.1006/jcss.2000.1727 ↩
-
Some Estimated Likelihoods for Computational Complexitydoi.org ↗主觀估計 ETH 為真約 70%,SETH 為真約 25%。https://doi.org/10.1007/978-3-319-91908-9_2 ↩
-
A simplified proof of ETH is falseshivakintali.github.io ↗對 OpenAI 證明主線的 22 頁簡化講解,只用稀疏化引理、線性代數和插值;第 2.4 節是本文復現的四變數例子。https://shivakintali.github.io/papers/ETH.pdf ↩ ↩2
-
anthropics/formal-math: ethgithub.com ↗Lean 4 形式化,入口是
MainResults.lean。https://github.com/anthropics/formal-math/tree/main/eth ↩ -
Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?techcrunch.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
-
The Exponential Time Hypothesis is Falsejohndcook.com ↗彙總三份證明連結;評論區提到 Lean 裡形式化的界比論文略弱。https://www.johndcook.com/blog/2026/10/27/eth-false/ ↩
-
The Octonionsarxiv.org ↗第 1 節講 Degen 1818 年、Graves 1843 年的八平方恆等式與八元數。https://arxiv.org/abs/math/0105155 ↩
-
Tensor Network Complexity of Multilinear Mapsarxiv.org ↗按一棵收縮樹計算這類求和的模型裡的下界;Anthropic 論文附錄 G 據此算出該模型下指數至少約為窮舉的 49%。https://arxiv.org/abs/1712.09630 ↩
-
Which Problems Have Strongly Exponential Complexity?doi.org ↗稀疏化引理:任意 3-CNF 可以寫成 2^(εn) 個子句數線性的公式之“或”。https://doi.org/10.1006/jcss.2001.1774 ↩