圖靈獎得主Avi Wigderson：P vs NP、零知識證明、量子計算，分別意味著是什么？

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

筆記來自軟件工程師Ryan Peterman主持的播客，2026年6月1日上線，時長接近兩個半小時。

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

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

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

一、P vs NP：一個關于人類能知道多少的問題

1、NP和P：驗證容易，求解未必容易

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

為什么說NP覆蓋了人類想解決的一切問題？因為不管是數學家尋找定理證明、科學家構建理論、工程師設計滿足約束的橋梁、偵探破案，這些活動都有一個共同前提：你至少得知道，找到答案的時候能認出它是答案。如果連這一點都做不到，那這件事根本不算一個你"真的想解決"的問題。

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

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

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

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

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

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

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

3、NP完全問題：攻破一個就攻破全部

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

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

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

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

4、理論上無解不等于實際中無解

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

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

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

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

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

先看一個基準?；氐角懊嬲f的布爾可滿足性問題，假設每個條件涉及三個變量，形式都是"這三個變量中至少有一個為真"。你什么都不看，隨機給每個變量拋硬幣決定真假。每個條件被違反的唯一情況是三個變量恰好全是假，概率是1/2 × 1/2 × 1/2 = 1/8。所以每個條件被滿足的概率是7/8，也就是87.5%。閉著眼睛猜，不用任何算法，就能滿足87.5%的條件。

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

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

二、時間和空間的隱秘關系：50年老墻被推倒

1、Ryan Williams 2025年的突破：時間t的計算只需要√t的空間

時間和空間是計算中兩種最基本的資源。時間是執行步數，空間是計算過程中需要的存儲單元數。兩者有一個顯然的關系：一次計算執行了多少步，最多就用多少個存儲單元，因為每一步最多訪問一個新單元?？臻g不會超過時間。

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

2025年2月，MIT的Ryan Williams證明：對于多帶圖靈機（理論計算機科學中建模通用計算的標準機器），空間上界可以壓縮到大約√t。還是100萬步的例子，從5萬個存儲單元降到1000個。代價是運行時間會大幅膨脹，但這個結果說明空間可以比時間小得多，兩者的關系遠不是"差不多大"這么簡單。

Williams的證明建立在James Cook（NP完全性理論創始人Steve Cook的兒子）和Ian Mertz的一個早期結果之上。

2、Barrington定理：用常數空間完成任意長度的計數

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

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

他第一次聽到這個結論時還是博士后，第一反應是"不可能"。但這個結果在密碼學里有重要用途，而且時間開銷僅為平方級，實際可用。

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

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

三、隨機性是觀察者的函數

1、隨機性的質量取決于誰在看：拋硬幣的三個實驗

Wigderson引用了密碼學先驅Blum和Micali論文中的一個思想實驗。同一枚硬幣從手指彈出，三種情況下你猜正反面的成功率完全不同。

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

三個實驗里，硬幣拋擲本身沒有任何變化。變的只有觀察者的計算能力。傳統定義把隨機性當作事件本身的屬性，復雜性理論的定義則聚焦于觀察者：對你來說有多少熵（不確定性），取決于你能調動多少計算資源來預測。同一個事件，對弱觀察者是隨機的，對強觀察者是確定的。

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

2、硬度 = 隨機性：一個看似不相關的等價關系

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

但這只是起點。原始的熵可能極小，也許只有極微弱的不確定性。要變成有用的偽隨機生成器，需要做兩件事：先放大硬度（把"1%的輸入猜不對"變成"50%的輸入猜不對"），讓隨機實例的答案對多項式時間觀察者來說接近50/50；再從少量真隨機種子擴展出大量偽隨機比特。

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

最終結論：如果存在某個問題確實需要天文數字級別的計算資源才能解決（這個假設比P ≠ NP更強但被廣泛相信），那么P = BPP成立，即任何高效的概率算法都有等效的高效確定性算法。換句話說，拋硬幣不會讓算法變得更強。隨機性在算法中的力量，可能沒有我們曾以為的那么大。

3、從概率到確定性的完整故事：素數判定

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

沒有人在這兩個算法上找到好答案。但2000年代初，印度計算機科學家Agrawal、Kayal和Saxena換了一條路，設計了一個不同的概率素數測試。因為新測試對隨機性的使用方式不同，分析之后發現它其實不需要所有比特完全獨立，結構化的偽隨機就夠用，最終用數論工具從少量比特生成了足夠的偽隨機序列，得到了確定性算法。

這個故事展示了一條路徑：有時候去隨機化的關鍵不是優化現有算法，而是設計一個新算法，使得對隨機性的依賴方式更容易被分析和替換。

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

現實世界的隨機源都不完美。天氣、股價、量子現象，這些都無法精確預測，但也不是完美隨機的：天氣有自相關，股價有趨勢，采樣總有偏差。

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

直接提取單個完美串是不可能的，因為你不知道熵藏在哪些比特里，沒法只挑好的。但可以生成大量候選串（比如幾千個），每個長度和原始數據中的真實不確定性大致相當，其中99%是真正的完美隨機。剩下1%是壞的，你不知道哪些壞。但這已經夠用了，把你的概率算法在每個候選串上跑一遍，取多數投票，壞串的影響會被淹沒。

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

困難問題能變成隨機性的來源。同樣的邏輯還能走得更遠：如果某些計算確實很難倒著做（比如把兩個大素數乘起來容易，把乘積分解回去極難），那就可以在此基礎上構建密碼系統和證明系統，讓人在不泄露秘密的前提下證明自己擁有秘密。這就是零知識證明的基礎，也是Wigderson最著名的貢獻之一。

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

Wigderson是零知識證明領域的奠基人之一。1985年，現代密碼學的奠基者Goldwasser、Micali和Rackoff三人定義了交互式證明和零知識的概念；1986年Wigderson與Goldreich、Micali一起證明了零知識證明的普遍性定理。Goldwasser和Micali后來因為密碼學的奠基性貢獻獲得了2012年圖靈獎。

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

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

零知識在交互式證明的基礎上加了一個要求：驗證者從整個交互中獲得的信息，除了"命題為真"這一事實之外，絕對為零。

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

2、圖著色協議：零知識如何運作

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

協議流程：證明者對每個頂點的顏色做一個密碼學承諾，效果類似把顏色放進密封信封。驗證者隨機選一條邊，證明者打開這條邊兩端的承諾。驗證者檢查兩個顏色是否合法且不同。重復多輪。

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

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

3、從圖著色到一切：NP完全性再次登場

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

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

Wigderson坦言他當年預言零知識證明永遠不會被工程實現，因為先把問題歸約到圖著色再走協議的開銷太大。結果他錯了。工程師們找到了更直接的方案，在更強或不同的假設下大幅簡化了協議。

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

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

五、量子計算到底改變了什么

1、Shor算法的沖擊波還在擴散

1994年，MIT數學家Peter Shor發現了高效的量子整數分解和離散對數算法（離散對數是和分解整數類似的另一類數學難題），直接威脅了當時（也是目前）幾乎所有公鑰密碼體系的安全基礎。公鑰密碼是讓兩個從沒見面的人也能安全通信的技術基礎，銀行轉賬、HTTPS網頁、電子簽名都靠它。自Shor算法發現以來，各國政府和企業投入了數十億資金建設量子計算的技術基礎設施。

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

Wigderson說，別說量子計算機了，如果明天有人找到一個經典的多項式時間分解算法，全世界就會陷入混亂，因為幾乎所有安全系統的基礎假設會同時崩潰。

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

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

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

3、MIP* = RE：復雜性理論產出了物理學和數學的定理

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

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

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

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

1、科學進展是蟻群協作，大突破罕見且不可預期

Wigderson把科學研究比作蟻群工程。每年的理論計算機科學會議上有幾百篇論文，絕大多數，包括他自己的絕大多數論文，都是在某個方向上做一點增量推進：改進一個界、發現一個技巧的變體、證明一個中等規模的定理。這些增量是必要的基礎設施。

偶爾有人發現一個根本性的新洞察，沖擊波傳遍整個領域。但你不能為了大突破而工作。做這些問題不是為了百萬美元獎金，百萬美元對這些問題來說根本不算什么。

2、理論計算機科學最核心的活動是建模

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

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

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

Wigderson說他不太有資格給建議，因為他主要是運氣好：好導師、好合作者、好社區。但他強調一點：在職業生涯初期發現自己的研究品味比追逐熱門問題更重要。讀不同領域的論文，嘗試不同類型的問題。往往你最喜歡做的事，就是你最擅長的事。

他講了一個細節：第一次參加理論計算機科學會議時他還是一年級博士生，有人把他介紹給NP完全性理論的奠基人之一Richard Karp，他說自己證明了某個問題是NP完全的，Karp真的對他的工作有興趣，認真問了細節。這個領域沒有等級壁壘，年輕人可以直接和大牛對話。

他對理論研究者的日常體驗也坦誠：大多數日子，你早上出門，晚上回來，什么也沒做成。他說的那段話放在了本文開頭。

總結

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

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

核心歸納

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

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

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