寫一篇自己也不完全懂的筆記。雖然不完全懂，但看完確實(shí)有收獲，懂的人應(yīng)該能收獲更多。
Avi Wigderson是人類歷史上唯一同時(shí)獲得圖靈獎(jiǎng)（2023年，計(jì)算機(jī)科學(xué)最高榮譽(yù)）和阿貝爾獎(jiǎng)（2021年，與László Lovász共享，數(shù)學(xué)領(lǐng)域最高榮譽(yù)之一）的學(xué)者。他是普林斯頓高等研究院IAS數(shù)學(xué)學(xué)院的Herbert H. Maass教授，研究領(lǐng)域覆蓋計(jì)算復(fù)雜性、隨機(jī)性理論、密碼學(xué)、圖論和量子計(jì)算。

筆記來自軟件工程師Ryan Peterman主持的播客，2026年6月1日上線，時(shí)長(zhǎng)接近兩個(gè)半小時(shí)。

為了便于理解，我整理了一條貫穿全場(chǎng)的主線，一句話總結(jié)就是：困難不只是障礙，困難本身是資源。NP完全問題極難求解（第一章），但正因?yàn)樗鼈冸y，答案對(duì)算力有限的觀察者來說就像隨機(jī)的，可以被當(dāng)作偽隨機(jī)比特來用（第三章）。同樣是因?yàn)槔щy問題存在，現(xiàn)代密碼學(xué)和零知識(shí)證明才有地基可以站（第四章）。量子計(jì)算威脅了其中一部分困難問題，所以需要找到連量子計(jì)算機(jī)都攻不破的新困難問題來重建地基（第五章）。

另有兩個(gè)旁支。第二章講的是計(jì)算資源之間的意外關(guān)系：時(shí)間和空間看起來差不多大，結(jié)果空間可以比時(shí)間小得多，50年的認(rèn)知在2025年被推翻。第六章講的是做這種研究的人怎么過日子：蟻群式協(xié)作、大多數(shù)日子一無所獲、建模比解題重要。

最后Wigderson被問什么人適合做理論研究，他說：你早上出門，晚上回來，什么也沒做成。你想做的事沒有進(jìn)展，想了一天，什么也沒想通。可是，如果你不享受這個(gè)過程本身，這個(gè)領(lǐng)域可能不適合你。

一、P vs NP：一個(gè)關(guān)于人類能知道多少的問題

1、NP和P：驗(yàn)證容易，求解未必容易

計(jì)算理論會(huì)把問題按解題所需的資源多少分成不同的類別，叫復(fù)雜性類。NP就是其中一個(gè)。NP的定義是：如果有人給出一個(gè)答案，我們能高效地驗(yàn)證它是否正確，這個(gè)問題就屬于NP。

為什么說NP覆蓋了人類想解決的一切問題？因?yàn)椴还苁菙?shù)學(xué)家尋找定理證明、科學(xué)家構(gòu)建理論、工程師設(shè)計(jì)滿足約束的橋梁、偵探破案，這些活動(dòng)都有一個(gè)共同前提：你至少得知道，找到答案的時(shí)候能認(rèn)出它是答案。如果連這一點(diǎn)都做不到，那這件事根本不算一個(gè)你"真的想解決"的問題。

P也是一個(gè)復(fù)雜性類。如果存在一個(gè)算法，不需要任何人給提示，自己就能在合理時(shí)間內(nèi)直接算出答案，這個(gè)問題就屬于P。手機(jī)上的導(dǎo)航app能算出任意兩點(diǎn)之間的最短路徑，不需要有人先告訴你走哪條路，算法自己能找到，所以最短路徑問題屬于P。

NP和P的區(qū)別在于：NP只要求你拿到答案后能判斷對(duì)不對(duì)，P要求你自己就能把答案算出來。這兩個(gè)類是否相等，是計(jì)算理論中最大的未解問題，叫P vs NP問題。P vs NP是問題的名字，P = NP和P ≠ NP是兩個(gè)可能的答案。

如果P = NP，意味著能驗(yàn)證就一定能求解，人類想知道的一切，從癌癥的治愈方案到任何數(shù)學(xué)猜想的證明，只要答案存在且可驗(yàn)證，就一定能被算法找到。如果P ≠ NP，意味著存在一些問題，答案可以被快速驗(yàn)證，但永遠(yuǎn)不可能被快速算出來。

2、所有NP問題背后是同一套邏輯

旅行商問題（找經(jīng)過所有城市的最短路線）、數(shù)獨(dú)、圖著色（給地圖著色讓相鄰區(qū)域顏色不同）、布爾可滿足性問題，這些看起來完全不同。布爾可滿足性這個(gè)名字拆開看："布爾"是說每個(gè)變量只能取真或假兩個(gè)值，"可滿足"是問能不能找到一組賦值讓所有條件同時(shí)成立。比如有三個(gè)條件"A或B為真""B或C為真""A和C不能同時(shí)為真"，能不能給A、B、C各指定真或假，讓三個(gè)條件全部滿足？這就是一個(gè)布爾可滿足性問題。但它們有一個(gè)共同點(diǎn)：驗(yàn)證答案是否正確的過程，都是計(jì)算機(jī)上一步一步的局部操作。

什么叫局部操作？不管什么計(jì)算設(shè)備，它每一步做的事都只涉及少數(shù)幾個(gè)比特：看這兩個(gè)數(shù)，加一下；看這個(gè)條件，判斷真假。把一次驗(yàn)證計(jì)算的所有步驟攤開成一張表，每個(gè)格子的狀態(tài)只取決于它旁邊的幾個(gè)格子。這種"每個(gè)格子都必須和鄰居一致"的要求，天然就是一組邏輯約束：給每個(gè)格子填一個(gè)值，使得所有相鄰格子之間的關(guān)系同時(shí)成立。

這意味著：任何NP問題的驗(yàn)證過程，不管表面上是在驗(yàn)證路線、驗(yàn)證著色還是驗(yàn)證蛋白質(zhì)構(gòu)型，都可以被翻譯成一組邏輯約束，也就是一個(gè)布爾可滿足性問題。以分解整數(shù)為例：有人給你兩個(gè)因子，你做一次乘法驗(yàn)證它們的乘積是否等于原來的數(shù)。乘法就是一系列局部操作（逐位相乘再進(jìn)位），每一步只涉及幾個(gè)數(shù)位。這些操作可以被寫成一組邏輯約束，所以"驗(yàn)證因子是否正確"可以被翻譯成一個(gè)可滿足性問題。

3、NP完全問題：攻破一個(gè)就攻破全部

上面這個(gè)事實(shí)有一個(gè)驚人的后果。既然任何NP問題都可以被翻譯成一個(gè)可滿足性問題，那如果你有一個(gè)高效的可滿足性求解器，你就自動(dòng)能高效求解所有NP問題。比如你要解一個(gè)旅行商問題：第一步，把城市、距離、約束條件按固定規(guī)則轉(zhuǎn)換成一組布爾變量和邏輯條件；第二步，交給可滿足性求解器，它給你一組真假賦值；第三步，按同樣的規(guī)則把這組賦值讀回一條路線。你拿到的就是旅行商問題的解。

可滿足性問題不是唯一有這種"萬能翻譯器"地位的問題。數(shù)獨(dú)、旅行商、圖著色也都有。假設(shè)你是一個(gè)數(shù)獨(dú)高手，任意尺寸的數(shù)獨(dú)都難不倒你。有人拿來一個(gè)旅行商問題（10個(gè)城市，找最短路線），你不會(huì)解。但存在一套固定的機(jī)械步驟，能把任何旅行商問題變成一道數(shù)獨(dú)題，而且從數(shù)獨(dú)的解可以反推出最短路線。如果你真能高效解任意數(shù)獨(dú)，你就自動(dòng)能高效解任意旅行商問題。

這類能充當(dāng)萬能翻譯器的問題叫NP完全問題。NP完全是貼在具體計(jì)算任務(wù)上的分類標(biāo)簽：旅行商、數(shù)獨(dú)、可滿足性各自是一個(gè)問題，"它是NP完全的"是數(shù)學(xué)家對(duì)這個(gè)問題做出的判定，意思是已經(jīng)證明了它具有萬能翻譯器的性質(zhì)。所有被判定為NP完全的問題難度完全相同：攻破一個(gè)就等于攻破全部。目前已知的NP完全問題有幾千個(gè)，分布在數(shù)學(xué)、物理、生物、工程、經(jīng)濟(jì)學(xué)各個(gè)領(lǐng)域。解不出來怎么知道有幾千個(gè)？因?yàn)榕卸ㄒ粋€(gè)問題有多難和解決這個(gè)問題是兩件事，就像你可以證明一塊巨石搬不動(dòng)，不需要真的搬動(dòng)它。過去五六十年里，成千上萬的研究者拼命想攻破哪怕一個(gè)，沒有人成功過。這是大多數(shù)理論計(jì)算機(jī)科學(xué)家相信P ≠ NP的最強(qiáng)理由。

但Wigderson話鋒一轉(zhuǎn)：這些全是直覺，不是證明。如果明天真有人想出全新的思路，找到了NP完全問題的高效算法，我們這些直覺一個(gè)也不算數(shù)。

4、理論上無解不等于實(shí)際中無解

前面說NP完全問題50年沒人攻破。是不是碰到這類問題就徹底沒辦法了？

不一定。NP完全說的是最壞情況：在所有可能的輸入里，存在某些極端的輸入，任何算法都沒法快速搞定。但你實(shí)際碰到的輸入未必是那些極端的。類比一下：數(shù)獨(dú)是NP完全問題（任意尺寸的），但你每天做的報(bào)紙上的9×9數(shù)獨(dú)總是能解的，因?yàn)槌鲱}人選的是有解且不太難的題目，你從來不會(huì)碰到理論上最壞的那些。

蛋白質(zhì)折疊是同樣的道理。蛋白質(zhì)是一條氨基酸鏈，合成之后會(huì)自動(dòng)折疊成能量最低的三維形狀。一條幾百個(gè)氨基酸的鏈，可能的折疊方式比宇宙中的原子還多，從中找到能量最低的那個(gè)構(gòu)型，這個(gè)問題被證明至少和NP完全問題一樣難（計(jì)算理論把這類問題叫NP難問題）。那人體折疊蛋白質(zhì)，是在解這個(gè)NP難題嗎？不是。人體只需要折疊進(jìn)化選中的那幾萬種蛋白質(zhì)，就像你只做報(bào)紙上的數(shù)獨(dú)，不做理論上最難的那些。進(jìn)化篩選出了容易折疊的蛋白質(zhì)，偏偏沒選中那些讓算法崩潰的鏈。

5、PCP定理：連近似解都不行

NP完全問題的精確解太難找。自然的退路是：我不追求滿足所有條件了，能不能滿足盡可能多的條件？比如一個(gè)布爾可滿足性問題有1000個(gè)條件，滿足全部太難，能不能找到一組賦值滿足其中950個(gè)？這就是近似解的思路。

先看一個(gè)基準(zhǔn)。回到前面說的布爾可滿足性問題，假設(shè)每個(gè)條件涉及三個(gè)變量，形式都是"這三個(gè)變量中至少有一個(gè)為真"。你什么都不看，隨機(jī)給每個(gè)變量拋硬幣決定真假。每個(gè)條件被違反的唯一情況是三個(gè)變量恰好全是假，概率是1/2 × 1/2 × 1/2 = 1/8。所以每個(gè)條件被滿足的概率是7/8，也就是87.5%。閉著眼睛猜，不用任何算法，就能滿足87.5%的條件。

PCP定理的一個(gè)推論（由復(fù)雜性理論家H?stad加強(qiáng)）說的是：想比隨機(jī)猜好哪怕一丁點(diǎn)，比如滿足87.6%的條件而不是87.5%，這件事的難度就跟找到滿足所有條件的精確解一模一樣，都是NP完全級(jí)別的。隨機(jī)猜的87.5%是免費(fèi)的天花板，想多邁一步就撞上NP完全的硬墻。連近似都沒有捷徑。

到這里，第一章講的都是哪些問題難、有多難、連近似都不行。接下來暫時(shí)離開這條線，看看計(jì)算資源之間的一個(gè)意外關(guān)系：時(shí)間和空間看起來差不多大，其實(shí)不是。

二、時(shí)間和空間的隱秘關(guān)系：50年老墻被推倒

1、Ryan Williams 2025年的突破：時(shí)間t的計(jì)算只需要√t的空間

時(shí)間和空間是計(jì)算中兩種最基本的資源。時(shí)間是執(zhí)行步數(shù)，空間是計(jì)算過程中需要的存儲(chǔ)單元數(shù)。兩者有一個(gè)顯然的關(guān)系：一次計(jì)算執(zhí)行了多少步，最多就用多少個(gè)存儲(chǔ)單元，因?yàn)槊恳徊阶疃嘣L問一個(gè)新單元。空間不會(huì)超過時(shí)間。

1975年，Hopcroft、Paul和Valiant三位計(jì)算理論家把這個(gè)上界改進(jìn)了一點(diǎn)點(diǎn)：空間可以從t壓縮到 t / log t。拿100萬步的計(jì)算來說，原來上界是100萬個(gè)存儲(chǔ)單元，他們壓縮到了大約5萬個(gè)。這個(gè)結(jié)果50年沒人打破，而且在某些受限計(jì)算模型里被證明是最優(yōu)的。

2025年2月，MIT的Ryan Williams證明：對(duì)于多帶圖靈機(jī)（理論計(jì)算機(jī)科學(xué)中建模通用計(jì)算的標(biāo)準(zhǔn)機(jī)器），空間上界可以壓縮到大約√t。還是100萬步的例子，從5萬個(gè)存儲(chǔ)單元降到1000個(gè)。代價(jià)是運(yùn)行時(shí)間會(huì)大幅膨脹，但這個(gè)結(jié)果說明空間可以比時(shí)間小得多，兩者的關(guān)系遠(yuǎn)不是"差不多大"這么簡(jiǎn)單。

Williams的證明建立在James Cook（NP完全性理論創(chuàng)始人Steve Cook的兒子）和Ian Mertz的一個(gè)早期結(jié)果之上。

2、Barrington定理：用常數(shù)空間完成任意長(zhǎng)度的計(jì)數(shù)

Wigderson講了一個(gè)他第一次聽說時(shí)完全不信的結(jié)果：如果你有一串比特想判斷0多還是1多，也就是計(jì)算理論里所說的多數(shù)表決問題，計(jì)數(shù)到n需要log n個(gè)比特來存儲(chǔ)（比如計(jì)數(shù)到1000需要10個(gè)比特，因?yàn)?的10次方是1024），這看起來就是下界。但David Barrington在1980年代發(fā)現(xiàn)，如果你可以隨機(jī)訪問輸入中的任何一個(gè)比特（意思是可以直接跳到第17個(gè)或第8100個(gè)，不用從頭往后讀），僅用常數(shù)空間，比如5個(gè)比特，就能完成任意長(zhǎng)度輸入的多數(shù)表決判斷。不管輸入有一千個(gè)比特還是一萬億個(gè)，5個(gè)比特的工作記憶就夠了。

這個(gè)結(jié)果的核心工具是非交換代數(shù)，也就是操作的順序會(huì)影響結(jié)果的數(shù)學(xué)結(jié)構(gòu)。具體做法是：看到1就做旋轉(zhuǎn)，看到0就做翻轉(zhuǎn)，這兩個(gè)操作作用在五個(gè)元素的排列上，先旋轉(zhuǎn)后翻轉(zhuǎn)和先翻轉(zhuǎn)后旋轉(zhuǎn)得到不同的結(jié)果。通過精心編排這些操作的順序，你可以用一種叫"交換子"的操作組合（先做A再做B再撤銷A再撤銷B）來模擬邏輯AND運(yùn)算。最終，一個(gè)布爾公式的計(jì)算被編碼在五個(gè)點(diǎn)的排列狀態(tài)里，只需要常數(shù)個(gè)比特就能記住。

他第一次聽到這個(gè)結(jié)論時(shí)還是博士后，第一反應(yīng)是"不可能"。但這個(gè)結(jié)果在密碼學(xué)里有重要用途，而且時(shí)間開銷僅為平方級(jí)，實(shí)際可用。

Wigderson還用了一個(gè)直覺謎題來解釋這種非交換操作為何能編碼計(jì)算：你有一幅畫，想用繩子掛在墻上的兩顆釘子上。兩顆釘子都在時(shí)畫掛著；拔掉任何一顆，畫就掉到地上。怎么繞繩子才能做到？?jī)深w釘子都需要才能掛住，這正好就是一個(gè)邏輯AND（兩個(gè)條件同時(shí)為真才輸出真），而它的解法就需要利用"繞了再反繞"的非交換操作。

回到主線。第一章把困難問題當(dāng)障礙看：NP完全問題50年沒人攻破，連近似都不行。但Wigderson獲圖靈獎(jiǎng)的核心貢獻(xiàn)恰恰是翻轉(zhuǎn)這個(gè)視角：困難問題不只是障礙，它本身是一種可以被利用的資源。邏輯是這樣的：如果一個(gè)問題的答案連最強(qiáng)的多項(xiàng)式時(shí)間算法都猜不出來，那這個(gè)答案對(duì)這些算法來說就像隨機(jī)的。"看起來隨機(jī)"不是一個(gè)缺陷，而是可以被拿來當(dāng)偽隨機(jī)比特用的材料。這就是第三章的起點(diǎn)。

三、隨機(jī)性是觀察者的函數(shù)

1、隨機(jī)性的質(zhì)量取決于誰在看：拋硬幣的三個(gè)實(shí)驗(yàn)

Wigderson引用了密碼學(xué)先驅(qū)Blum和Micali論文中的一個(gè)思想實(shí)驗(yàn)。同一枚硬幣從手指彈出，三種情況下你猜正反面的成功率完全不同。

第一種情況，你裸眼看，成功率1/2，這就是經(jīng)典的隨機(jī)事件。第二種情況，你面前有一臺(tái)筆記本電腦，但硬幣一秒就落地，來不及計(jì)算，成功率還是約1/2。第三種情況，你的電腦連著一臺(tái)Cray超級(jí)計(jì)算機(jī)，超算連著一堆對(duì)準(zhǔn)硬幣的傳感器和相機(jī)，能在硬幣離開手指的瞬間測(cè)量所有角動(dòng)量、空氣濕度、距離等參數(shù)，在硬幣落地前算出結(jié)果。成功率接近100%。

三個(gè)實(shí)驗(yàn)里，硬幣拋擲本身沒有任何變化。變的只有觀察者的計(jì)算能力。傳統(tǒng)定義把隨機(jī)性當(dāng)作事件本身的屬性，復(fù)雜性理論的定義則聚焦于觀察者：對(duì)你來說有多少熵（不確定性），取決于你能調(diào)動(dòng)多少計(jì)算資源來預(yù)測(cè)。同一個(gè)事件，對(duì)弱觀察者是隨機(jī)的，對(duì)強(qiáng)觀察者是確定的。

但這個(gè)原則有邊界。Wigderson引用了Shannon定理：如果你要生成密碼或密鑰，密碼的安全性等于其中的真實(shí)熵。這時(shí)候你需要的是信息論意義上的真隨機(jī)，不是"對(duì)某個(gè)算法來說看起來隨機(jī)"。生成一個(gè)真隨機(jī)比特就是生成一個(gè)真隨機(jī)比特，你的計(jì)算能力再?gòu)?qiáng)也替代不了這個(gè)需求。

2、硬度 = 隨機(jī)性：一個(gè)看似不相關(guān)的等價(jià)關(guān)系

如果你面對(duì)一個(gè)NP難問題的實(shí)例，作為一個(gè)多項(xiàng)式時(shí)間算法（運(yùn)行步數(shù)是輸入長(zhǎng)度的某個(gè)多項(xiàng)式倍數(shù)，比如n2或n3，而不是2的n次方），你猜不出答案。答案對(duì)你來說就有熵。這就是"困難問題蘊(yùn)含隨機(jī)性"的起點(diǎn)：既然你算不出來，那個(gè)答案對(duì)你來說就像隨機(jī)的。

但這只是起點(diǎn)。原始的熵可能極小，也許只有極微弱的不確定性。要變成有用的偽隨機(jī)生成器，需要做兩件事：先放大硬度（把"1%的輸入猜不對(duì)"變成"50%的輸入猜不對(duì)"），讓隨機(jī)實(shí)例的答案對(duì)多項(xiàng)式時(shí)間觀察者來說接近50/50；再?gòu)纳倭空骐S機(jī)種子擴(kuò)展出大量偽隨機(jī)比特。

Wigderson和Nisan設(shè)計(jì)了一種叫NW生成器的裝置來完成后半段工作。它的原理可以這樣理解：你有一個(gè)連多項(xiàng)式時(shí)間算法都算不出的困難函數(shù)，你只需要一小段真隨機(jī)種子（比如10個(gè)比特），從中按照不同的規(guī)則挑出若干子集（比如挑出第1、3、7號(hào)比特作為一組，第2、5、8號(hào)作為另一組），把每組喂給困難函數(shù)得到一個(gè)輸出位。因?yàn)楹瘮?shù)對(duì)多項(xiàng)式時(shí)間算法來說不可預(yù)測(cè)，每個(gè)輸出位對(duì)它來說都像隨機(jī)的。雖然這些輸出位之間其實(shí)高度相關(guān)（它們共享種子），但沒有高效算法能檢測(cè)到這種相關(guān)性。這樣你就從10個(gè)真隨機(jī)比特"膨脹"出了遠(yuǎn)多于10個(gè)的偽隨機(jī)比特。

最終結(jié)論：如果存在某個(gè)問題確實(shí)需要天文數(shù)字級(jí)別的計(jì)算資源才能解決（這個(gè)假設(shè)比P ≠ NP更強(qiáng)但被廣泛相信），那么P = BPP成立，即任何高效的概率算法都有等效的高效確定性算法。換句話說，拋硬幣不會(huì)讓算法變得更強(qiáng)。隨機(jī)性在算法中的力量，可能沒有我們?cè)詾榈哪敲创蟆?/p>

3、從概率到確定性的完整故事：素?cái)?shù)判定

素?cái)?shù)判定這個(gè)問題，高斯在幾百年前就想要一個(gè)高效的判定方法，但長(zhǎng)期沒有人找到。1970年代，Solovay-Strassen和Miller-Rabin分別發(fā)明了概率性素?cái)?shù)測(cè)試：給一個(gè)數(shù)，算法靠拋硬幣做隨機(jī)抽查，如果通過了多輪抽查就報(bào)告"極大概率是素?cái)?shù)"，如果某輪沒通過就確定"不是素?cái)?shù)"。速度快，但依賴完美隨機(jī)比特。人們開始追問：能不能用更少的、有結(jié)構(gòu)的隨機(jī)性來替代？

沒有人在這兩個(gè)算法上找到好答案。但2000年代初，印度計(jì)算機(jī)科學(xué)家Agrawal、Kayal和Saxena換了一條路，設(shè)計(jì)了一個(gè)不同的概率素?cái)?shù)測(cè)試。因?yàn)樾聹y(cè)試對(duì)隨機(jī)性的使用方式不同，分析之后發(fā)現(xiàn)它其實(shí)不需要所有比特完全獨(dú)立，結(jié)構(gòu)化的偽隨機(jī)就夠用，最終用數(shù)論工具從少量比特生成了足夠的偽隨機(jī)序列，得到了確定性算法。

這個(gè)故事展示了一條路徑：有時(shí)候去隨機(jī)化的關(guān)鍵不是優(yōu)化現(xiàn)有算法，而是設(shè)計(jì)一個(gè)新算法，使得對(duì)隨機(jī)性的依賴方式更容易被分析和替換。

4、隨機(jī)性純化：從噪聲中提煉出真隨機(jī)

現(xiàn)實(shí)世界的隨機(jī)源都不完美。天氣、股價(jià)、量子現(xiàn)象，這些都無法精確預(yù)測(cè)，但也不是完美隨機(jī)的：天氣有自相關(guān)，股價(jià)有趨勢(shì)，采樣總有偏差。

隨機(jī)性提取理論要解決的問題是：給你一堆不完美的隨機(jī)比特，能不能從中提煉出接近完美的隨機(jī)比特？

直接提取單個(gè)完美串是不可能的，因?yàn)槟悴恢漓夭卦谀男┍忍乩铮瑳]法只挑好的。但可以生成大量候選串（比如幾千個(gè)），每個(gè)長(zhǎng)度和原始數(shù)據(jù)中的真實(shí)不確定性大致相當(dāng)，其中99%是真正的完美隨機(jī)。剩下1%是壞的，你不知道哪些壞。但這已經(jīng)夠用了，把你的概率算法在每個(gè)候選串上跑一遍，取多數(shù)投票，壞串的影響會(huì)被淹沒。

在多源提取的場(chǎng)景中，如果你有多個(gè)互不相關(guān)的弱隨機(jī)源，一個(gè)關(guān)鍵工具來自算術(shù)組合學(xué)中的和積定理。這個(gè)定理說的是：對(duì)任意一組K個(gè)整數(shù)，要么把它們兩兩相加能得到遠(yuǎn)多于K個(gè)不同的和，要么把它們兩兩相乘能得到遠(yuǎn)多于K個(gè)不同的積。至少有一種操作能讓集合急劇膨脹。加法和乘法在這個(gè)意義上是"正交"的，一種不膨脹，另一種必定膨脹。利用這個(gè)性質(zhì)，把幾個(gè)弱隨機(jī)源的輸出當(dāng)成數(shù)字做混合運(yùn)算，就能讓輸出的不確定性（熵）超過任何單個(gè)輸入源，逐步逼近完美隨機(jī)。

困難問題能變成隨機(jī)性的來源。同樣的邏輯還能走得更遠(yuǎn)：如果某些計(jì)算確實(shí)很難倒著做（比如把兩個(gè)大素?cái)?shù)乘起來容易，把乘積分解回去極難），那就可以在此基礎(chǔ)上構(gòu)建密碼系統(tǒng)和證明系統(tǒng)，讓人在不泄露秘密的前提下證明自己擁有秘密。這就是零知識(shí)證明的基礎(chǔ)，也是Wigderson最著名的貢獻(xiàn)之一。

四、零知識(shí)證明：什么都不泄露，但讓你完全信服

Wigderson是零知識(shí)證明領(lǐng)域的奠基人之一。1985年，現(xiàn)代密碼學(xué)的奠基者Goldwasser、Micali和Rackoff三人定義了交互式證明和零知識(shí)的概念；1986年Wigderson與Goldreich、Micali一起證明了零知識(shí)證明的普遍性定理。Goldwasser和Micali后來因?yàn)槊艽a學(xué)的奠基性貢獻(xiàn)獲得了2012年圖靈獎(jiǎng)。

1、零知識(shí)的含義：比"不泄露密碼"深刻得多

前面說NP問題的特點(diǎn)是答案可以被高效驗(yàn)證。換一種說法：有人聲稱有答案（證明者），把答案寫下來（證明），你檢查一遍（驗(yàn)證者）。這就是一個(gè)證明系統(tǒng)。經(jīng)典的NP證明是單向的：證明者寫完，驗(yàn)證者讀完，結(jié)束。交互式證明把這個(gè)過程變成對(duì)話：證明者和驗(yàn)證者可以來回提問和回答，驗(yàn)證者可以拋硬幣做隨機(jī)挑戰(zhàn)，最終以極高概率確信證明者的聲明為真。

零知識(shí)在交互式證明的基礎(chǔ)上加了一個(gè)要求：驗(yàn)證者從整個(gè)交互中獲得的信息，除了"命題為真"這一事實(shí)之外，絕對(duì)為零。

Wigderson說，這聽起來荒謬透頂。想象有人說證明了P ≠ NP，你跟他交互之后完全相信他確實(shí)證明了，但你對(duì)證明方法一無所知。怎么可能有人讓你相信他證明了P ≠ NP，而你結(jié)束對(duì)話時(shí)對(duì)證明方式一無所知，只知道對(duì)方確實(shí)做到了？

2、圖著色協(xié)議：零知識(shí)如何運(yùn)作

Wigderson用三著色問題演示了零知識(shí)證明的核心思路。證明者聲稱能用三種顏色為一張圖著色，使得每條邊的兩個(gè)端點(diǎn)顏色不同。

協(xié)議流程：證明者對(duì)每個(gè)頂點(diǎn)的顏色做一個(gè)密碼學(xué)承諾，效果類似把顏色放進(jìn)密封信封。驗(yàn)證者隨機(jī)選一條邊，證明者打開這條邊兩端的承諾。驗(yàn)證者檢查兩個(gè)顏色是否合法且不同。重復(fù)多輪。

正確性容易理解：如果圖不是三可著色的，無論證明者怎么承諾，至少有一條邊是錯(cuò)的，驗(yàn)證者有非零概率選中它。重復(fù)幾千輪，作弊者逃脫的概率指數(shù)級(jí)趨近于零。

零知識(shí)性的關(guān)鍵在于：證明者每輪都隨機(jī)把紅綠藍(lán)三種顏色重新洗牌，比如這輪紅變綠、綠變藍(lán)、藍(lán)變紅，下輪又換一種排列，一共有六種排列方式。在這種均勻隨機(jī)的顏色洗牌下，驗(yàn)證者看到的任何一條邊的兩個(gè)顏色，都只是"兩個(gè)不同的隨機(jī)顏色"。驗(yàn)證者自己隨機(jī)抽兩個(gè)不同顏色就能得到同樣的分布。每輪學(xué)到的信息量為零。

3、從圖著色到一切：NP完全性再次登場(chǎng)

三著色是NP完全問題。通過歸約（前面說的"問題翻譯"），任何NP命題都能被轉(zhuǎn)換成一個(gè)三著色問題的實(shí)例。而且歸約不僅保持命題的真假，還保持證明的可翻譯性：如果你有原問題的證明，就能構(gòu)造出對(duì)應(yīng)圖的合法三著色方案。

所以，任何可以被數(shù)學(xué)證明的命題，都有零知識(shí)交互式證明。密碼學(xué)、區(qū)塊鏈、隱私計(jì)算中大量使用的零知識(shí)技術(shù)，根基就在這里。

Wigderson坦言他當(dāng)年預(yù)言零知識(shí)證明永遠(yuǎn)不會(huì)被工程實(shí)現(xiàn)，因?yàn)橄劝褑栴}歸約到圖著色再走協(xié)議的開銷太大。結(jié)果他錯(cuò)了。工程師們找到了更直接的方案，在更強(qiáng)或不同的假設(shè)下大幅簡(jiǎn)化了協(xié)議。

2025年7月，IAS博士后Rahul Ilango發(fā)表了一項(xiàng)成果。前面講的圖著色協(xié)議需要證明者和驗(yàn)證者反復(fù)對(duì)話好幾千輪，還需要雙方事先共享一些公共參數(shù)（叫可信設(shè)置）。Ilango利用哥德爾不完備性定理的思想（存在真但不可證的命題），構(gòu)造出了一種零知識(shí)證明系統(tǒng)：證明者只需要發(fā)送一條消息，驗(yàn)證者獨(dú)立檢查就行，不需要對(duì)話；也不需要任何事先約定的公共參數(shù)；而且如果命題為假，根本不可能存在能騙過驗(yàn)證者的假證明。

第三章和第四章的一切，從偽隨機(jī)生成器到零知識(shí)證明到整個(gè)公鑰密碼體系，都建立在一個(gè)假設(shè)上：某些問題確實(shí)很難解。如果這個(gè)假設(shè)被推翻，地基就沒了。量子計(jì)算正是對(duì)這個(gè)假設(shè)最大的威脅。

五、量子計(jì)算到底改變了什么

1、Shor算法的沖擊波還在擴(kuò)散

1994年，MIT數(shù)學(xué)家Peter Shor發(fā)現(xiàn)了高效的量子整數(shù)分解和離散對(duì)數(shù)算法（離散對(duì)數(shù)是和分解整數(shù)類似的另一類數(shù)學(xué)難題），直接威脅了當(dāng)時(shí)（也是目前）幾乎所有公鑰密碼體系的安全基礎(chǔ)。公鑰密碼是讓兩個(gè)從沒見面的人也能安全通信的技術(shù)基礎(chǔ)，銀行轉(zhuǎn)賬、HTTPS網(wǎng)頁(yè)、電子簽名都靠它。自Shor算法發(fā)現(xiàn)以來，各國(guó)政府和企業(yè)投入了數(shù)十億資金建設(shè)量子計(jì)算的技術(shù)基礎(chǔ)設(shè)施。

在硬件層面，量子比特需要保持在疊加態(tài)才能做量子計(jì)算，這種狀態(tài)叫相干性，極其脆弱。經(jīng)典計(jì)算機(jī)的硬件錯(cuò)誤率低到基本可以忽略，Intel芯片甚至不需要內(nèi)置糾錯(cuò)。量子系統(tǒng)則不同，量子力學(xué)里"一切影響一切"，外界噪聲會(huì)不斷干擾計(jì)算，量子糾錯(cuò)碼只是解決方案的一部分。

Wigderson說，別說量子計(jì)算機(jī)了，如果明天有人找到一個(gè)經(jīng)典的多項(xiàng)式時(shí)間分解算法，全世界就會(huì)陷入混亂，因?yàn)閹缀跛邪踩到y(tǒng)的基礎(chǔ)假設(shè)會(huì)同時(shí)崩潰。

2、后量子密碼學(xué)：重建安全的地基

因?yàn)镾hor算法的存在，密碼學(xué)界需要找到即使面對(duì)量子計(jì)算機(jī)也無法高效攻破的數(shù)學(xué)難題。要構(gòu)建公鑰系統(tǒng)，需要一種特殊的單向函數(shù)叫陷門函數(shù)：正著算容易，倒著算極難，但持有一把"密鑰"（陷門）的人可以倒著算。這種函數(shù)本身就稀缺。已知的只有分解整數(shù)、離散對(duì)數(shù)，以及1990年代匈牙利計(jì)算機(jī)科學(xué)家Ajtai基于格問題提出的方案及其衍生變體。格問題是一類高維空間中的幾何難題，比如在一個(gè)由規(guī)則排列的點(diǎn)構(gòu)成的無限點(diǎn)陣（格）中，找到離原點(diǎn)最近的那個(gè)點(diǎn)。

Shor算法之所以有效，核心在于它把分解和離散對(duì)數(shù)問題歸約為周期查找問題，而量子計(jì)算機(jī)可以同時(shí)處理所有可能的輸入（疊加態(tài)），然后用一種叫量子傅里葉變換的操作讓正確答案的信號(hào)互相增強(qiáng)、錯(cuò)誤答案的信號(hào)互相抵消，從而高效地找到周期。但格問題至今沒有人找到高效的量子算法。NSA等機(jī)構(gòu)正在推動(dòng)全球向抗量子密碼遷移。

3、MIP* = RE：復(fù)雜性理論產(chǎn)出了物理學(xué)和數(shù)學(xué)的定理

大約在2020年初，Ji、Natarajan、Vidick、Wright和Yuen五位來自悉尼科技大學(xué)、加州理工和多倫多大學(xué)的研究者證明了一件事：如果證明系統(tǒng)中有多個(gè)量子證明者（他們之間有量子糾纏），那么一個(gè)高效的經(jīng)典驗(yàn)證者能夠驗(yàn)證的問題范圍，包括了停機(jī)問題這種根本不可計(jì)算的問題。停機(jī)問題就是判斷一段給定的程序到底會(huì)在有限步內(nèi)停下來還是永遠(yuǎn)跑下去，圖靈在1936年證明了不存在能解決所有情況的通用算法。計(jì)算理論把這個(gè)結(jié)論記為MIP* = RE。

Wigderson承認(rèn)這聽起來像是復(fù)雜性理論家在沙盤里堆城堡。但這篇約165頁(yè)的論文立刻解決了數(shù)學(xué)和物理中多個(gè)懸了幾十年的猜想，包括純數(shù)學(xué)中的Connes嵌入猜想和量子物理中的Tsirelson問題。搞復(fù)雜性理論的人造出的工具，解決了數(shù)學(xué)家和物理學(xué)家用自己的方法長(zhǎng)期解決不了的問題。而且這只是開始，基于同樣技術(shù)的后續(xù)論文正在解決更多數(shù)學(xué)猜想。

從P vs NP到量子計(jì)算，Wigderson的職業(yè)生涯跨越了計(jì)算理論最核心的幾個(gè)問題。播客的最后，他聊了聊做這種研究是什么體驗(yàn)。

六、做理論研究的人怎么過日子

1、科學(xué)進(jìn)展是蟻群協(xié)作，大突破罕見且不可預(yù)期

Wigderson把科學(xué)研究比作蟻群工程。每年的理論計(jì)算機(jī)科學(xué)會(huì)議上有幾百篇論文，絕大多數(shù)，包括他自己的絕大多數(shù)論文，都是在某個(gè)方向上做一點(diǎn)增量推進(jìn)：改進(jìn)一個(gè)界、發(fā)現(xiàn)一個(gè)技巧的變體、證明一個(gè)中等規(guī)模的定理。這些增量是必要的基礎(chǔ)設(shè)施。

偶爾有人發(fā)現(xiàn)一個(gè)根本性的新洞察，沖擊波傳遍整個(gè)領(lǐng)域。但你不能為了大突破而工作。做這些問題不是為了百萬美元獎(jiǎng)金，百萬美元對(duì)這些問題來說根本不算什么。

2、理論計(jì)算機(jī)科學(xué)最核心的活動(dòng)是建模

比起"解題"，Wigderson更強(qiáng)調(diào)"建模"的重要性。解題是在已有的框架里工作：?jiǎn)栴}已經(jīng)定義好了，你去證明或者找答案。建模是創(chuàng)造框架本身：在你建模之前，用來表述問題的概念還不存在。前面提到的好幾個(gè)突破都是建模貢獻(xiàn)：Cook和Levin不是解了一道題，而是創(chuàng)造了NP完全性這個(gè)分類框架，讓幾千個(gè)看似無關(guān)的問題被識(shí)別為同一難度；Goldwasser和Micali不是證了一個(gè)定理，而是發(fā)明了"交互式證明"這個(gè)模型，零知識(shí)證明才有了可能。

他拿隨機(jī)性舉例：傳統(tǒng)定義聚焦于事件本身是否隨機(jī)，復(fù)雜性理論的定義聚焦于觀察者的計(jì)算能力。這不是在舊定義下解了一道題，是把"隨機(jī)"這個(gè)詞的意思換了，然后一整個(gè)新領(lǐng)域（偽隨機(jī)性、去隨機(jī)化）從新定義里長(zhǎng)出來了。定義一個(gè)好的概念，比在舊概念里證一個(gè)新定理，影響范圍大得多。

3、給年輕研究者的建議：在早期階段做你最享受的事

Wigderson說他不太有資格給建議，因?yàn)樗饕沁\(yùn)氣好：好導(dǎo)師、好合作者、好社區(qū)。但他強(qiáng)調(diào)一點(diǎn)：在職業(yè)生涯初期發(fā)現(xiàn)自己的研究品味比追逐熱門問題更重要。讀不同領(lǐng)域的論文，嘗試不同類型的問題。往往你最喜歡做的事，就是你最擅長(zhǎng)的事。

他講了一個(gè)細(xì)節(jié)：第一次參加理論計(jì)算機(jī)科學(xué)會(huì)議時(shí)他還是一年級(jí)博士生，有人把他介紹給NP完全性理論的奠基人之一Richard Karp，他說自己證明了某個(gè)問題是NP完全的，Karp真的對(duì)他的工作有興趣，認(rèn)真問了細(xì)節(jié)。這個(gè)領(lǐng)域沒有等級(jí)壁壘，年輕人可以直接和大牛對(duì)話。

他對(duì)理論研究者的日常體驗(yàn)也坦誠(chéng)：大多數(shù)日子，你早上出門，晚上回來，什么也沒做成。他說的那段話放在了本文開頭。

總結(jié)

P vs NP是關(guān)于人類知識(shí)邊界的哲學(xué)命題，但它有精確的數(shù)學(xué)表述和具體的工程后果。隨機(jī)性不是事物的屬性，而是觀察者與事物之間關(guān)系的屬性，但這個(gè)哲學(xué)洞察直接通向可證明的去隨機(jī)化定理。零知識(shí)證明聽起來像邏輯悖論，但它有嚴(yán)格的協(xié)議、可量化的安全保證和已經(jīng)在鏈上運(yùn)行的實(shí)現(xiàn)。

對(duì)于關(guān)注AI和計(jì)算前沿的讀者：第一，后量子密碼遷移不是遠(yuǎn)期問題，如果明天有人找到經(jīng)典分解算法（不需要量子計(jì)算機(jī)），現(xiàn)有安全體系立刻崩塌。第二，復(fù)雜性理論在過去五年里（MIP* = RE、Ryan Williams的時(shí)空定理、Ilango的零知識(shí)突破）產(chǎn)出了一連串將理論邊界大幅推移的結(jié)果，這些結(jié)果對(duì)密碼學(xué)、安全系統(tǒng)、甚至物理學(xué)基礎(chǔ)問題都有實(shí)質(zhì)性影響。

核心歸納

Q1: P vs NP到底在問什么？NP是所有"答案可以被高效驗(yàn)證"的問題，直覺上對(duì)應(yīng)人類真正想解決的一切問題。P是已經(jīng)能被高效求解的子集。P vs NP問的是：驗(yàn)證的容易是否蘊(yùn)含求解的容易？如果P = NP，人類想知道的一切（只要答案存在且可驗(yàn)證）都能被算法找到。幾乎所有理論計(jì)算機(jī)科學(xué)家認(rèn)為P ≠ NP，但50年來沒有人能證明這一點(diǎn)。

Q2: 隨機(jī)性在算法中真的有用嗎？有用但可能沒那么有用。在"困難問題確實(shí)存在"的假設(shè)下（比P ≠ NP稍強(qiáng)），任何高效概率算法都有等效的高效確定性算法（P = BPP）。核心洞察是隨機(jī)性的質(zhì)量取決于觀察者的計(jì)算能力，對(duì)多項(xiàng)式時(shí)間算法來說"看起來隨機(jī)"的序列不需要真的隨機(jī)，只要沒有算法能分辨真假即可。但這有邊界：密碼學(xué)中需要信息論安全的場(chǎng)景仍然依賴真隨機(jī)。"硬度等價(jià)于隨機(jī)性"的范式是Wigderson獲圖靈獎(jiǎng)的核心貢獻(xiàn)之一。

Q3: 零知識(shí)證明為什么重要？零知識(shí)證明讓你在完全不泄露任何秘密的前提下，讓對(duì)方相信你確實(shí)擁有某個(gè)秘密或完成了某個(gè)計(jì)算。Wigderson等人1986年證明的普遍性定理說：任何NP命題都有零知識(shí)交互式證明。這意味著密碼協(xié)議中任何"我做了該做的事但不想讓你看到細(xì)節(jié)"的需求，理論上都有解決方案。今天區(qū)塊鏈和隱私計(jì)算中大量使用的ZK技術(shù)，根基在此。