來源：zzllrr小樂

作者：Ryan Peterman

近日，圖靈獎與阿貝爾獎雙料得主艾維?維格德森（Avi Wigderson）接受瑞安·彼得曼（Ryan Peterman，Ins前工程師、播客主）專訪，就P與NP問題、零知識證明、量子計算展開討論。幾年前Avi Wigderson患淋巴瘤癌癥并積極接受治療，順利康復后不久，分別斬獲阿貝爾獎和圖靈獎。

圖源：Ryan Peterman @YouTube

• 第一章：引言

• 第二章：P 與 NP 問題

• 第三章：放寬正確性約束會怎樣

• 第四章：NP 完全問題為何彼此等價

• 第五章：時間復雜度與空間復雜度

• 第六章：為何業界廣泛使用可滿足性求解器

• 第七章：隨機性也是一種計算資源

• 第八章：隨機性依賴于觀測者的計算能力

• 第九章：零知識證明及其意義

• 第十章：量子計算帶來的變革

• 第十一章：數學與計算機科學的關系

• 第十二章：科研生涯中的重大突破

• 第十三章：給年輕時的自己的建議

• 第十四章：結束語

作者：瑞安·彼得曼（Ryan Peterman，Ins前工程師，播客主）2026-6-1

譯者：zzllrr小樂（數學科普公眾號）2026-6-3

第一章：引言

倘若未來有人找到了可在多項式時間內運行的經典整數分解算法，我認為整個世界都會陷入混亂。

本期嘉賓是艾維?維格德森（Avi Wigderson），圖靈獎與阿貝爾獎雙料得主。本次訪談，我和他深入探討了他所研究的領域。

P 與 NP 問題，本質上關乎我們能否解開所有真正想要攻克的難題。隨機性的優劣，取決于觀測者本身，更取決于觀測者的計算能力。如果有人宣稱證明了 P 不等于 NP，要如何讓我信服？可即便如此，我對他們的證明思路依舊一無所知。要知道，就連不可計算類的問題，他們也能找到對應的解決辦法。試想，假如某天有人攻克了 NP 完全問題的高效解法，我們的世界又會變成什么樣？

以下是本期完整訪談內容。

第二章：P與NP問題

問：您在一場講座中提到，從哲學層面來講，P 與 NP 問題觸及了人類認知的終極邊界。那么 P 與 NP 問題究竟是什么？它又和人類認知有著怎樣的關聯？

我用通俗易懂的方式，從宏觀層面來講。生活中存在各式各樣的問題：數學難題、科學課題、醫學難題、個人瑣事、各類智力問題。計算機科學的核心，就是用計算機來解決問題。我們嘗試對可求解的問題進行分類，以此厘清人類認知的邊界。能被我們解開的問題，就是我們能夠掌握、理解的內容，而人類想要探索的問題數不勝數。

首先來說 NP 類問題，人類所有想要解答的問題，基本都歸屬于 NP 范疇。在 NP 問題集合中，又劃分出一個子集，也就是我們目前能夠實際求解的問題。而我們真正關注的，是理論上所有可被求解的問題。

因此，P 與 NP 的核心命題就是：我們是否有能力解開所有渴望解答的難題，是否能夠知曉一切想要探尋的真相。這一問題，直指人類認知的極限。

接下來我解釋一下這些數學定義的類別為何對應這樣直觀的含義。先看 P 類問題：所謂可求解，指的是借助現有設備與高效算法，在有限時間內得出答案。手機里各類應用就是典型例子，比如導航軟件，背后就有一套高效算法，能夠在任意地圖上計算出兩點之間的最短路徑，這類問題都屬于 P 類。

而人類想要探究的問題，大多屬于 NP 類。NP 類問題的定義是：我們暫時無法判斷求解難度，但如果有人給出了一個答案，我們可以輕松驗證這個答案是否正確。

為何人類探索的所有問題都具備這一特征？不妨換位思考：人若是下定決心鉆研一個問題，最基本的前提就是，當你找到答案時，能夠識別出這就是正解。倘若即便找到了答案也無從分辨，那人們根本不會著手去尋找。

數學家鉆研定理證明，他人寫出證明過程，我們就能核驗真偽；科學家研究行星、細菌等各類數據，構建理論學說，理論必須與觀測數據相符，我們也能判斷這套理論是否成立；工程師承接項目，在資金、物理條件等各類約束下設計橋梁、電子設備等產品，委托方可以直觀檢查成品是否符合要求；偵探偵破案件，最終梳理出的案情邏輯也能被大眾驗證。

類似的例子還有很多。人類幾乎所有重要的探索活動，都遵循同一個規律：答案一旦出現，便能被輕松識別。

總結來說：

NP 代表人類所有想要解答的問題，P 代表人類能夠實際求解的問題。二者是否等價，就是 P 與 NP 問題的核心。

如果 P 等于 NP，那就意味著：只要一個答案能夠被輕松驗證，我們就一定能高效找到它。攻克癌癥、破解各類難題，所有想象得到的目標都有實現的可能，人類將能夠洞悉一切想了解的事物。這無疑是關乎人類認知本質的終極問題。

問：這也是七大千禧年大獎難題之一，破解該問題就能獲得百萬美元獎金。這個問題存在兩種可能性：證明 P 與 NP 等價，或是證明二者不等價。如果讓你憑直覺預測，未來究竟會得出哪一種結論？原因是什么？

包括我在內，幾乎所有理論計算機領域的學者都傾向于認為P 不等于 NP，不過支撐這個觀點的理由，其實并不算絕對嚴謹。

第一點，來自生活直覺：尋找答案的過程，遠比驗證答案要困難。舉個例子，你弄丟了鑰匙或手機，四處尋覓毫無頭緒，但如果有人告訴你東西放在窗臺，你一眼就能確認。現實經驗告訴我們，“尋找” 往往難于 “核驗”。

第二點，NP 類問題在各個領域無處不在：優化問題、邏輯問題、數學問題，還有算法、協議、安全系統的可靠性驗證等等，其中大量都屬于 NP 問題甚至 NP 難問題。過去六七十年間，無數研究者針對不同場景下的這類問題，嘗試尋找高效算法，最終全都無功而返。這似乎暗示著，通用的高效解法并不存在。

從技術層面來講，NP 問題（尤其是 NPC——NP完全問題），往往需要在指數級規模的解空間中逐一檢索。P 與 NP 之爭，本質就是能否找到一種巧妙的通用方法，把指數級的檢索范圍壓縮到合理區間 —— 如果能做到，就證明 P 等于 NP。但目前學界普遍認為，這樣的方法并不存在。

當然這些都只是基于經驗的推測。倘若某天有人憑借全新思路，找到了 NP 完全問題的高效算法，整個世界都會被徹底改變。

問：在軟件工程領域，我們一直在使用各類算法。很多難題原本只能依靠暴力枚舉，復雜度極高，而優秀的算法能將其轉化為多項式時間可解的問題。但面對 NP 問題，目前最優的解法依舊逃不開暴力枚舉，我這樣理解是否正確？

你的理解完全準確。具體來說，一個 NP 完全問題會包含無數個具體實例，比如旅行商問題，對應著各式各樣的地圖與路網。我們評判一套算法是否高效，標準是它能否對所有實例都做到高效且正確求解。

但軟件工程、現實優化場景中，人們遇到的往往只是一小部分特殊實例。舉個例子，協議驗證、生物學中的蛋白質折疊問題，都屬于 NP 難問題。蛋白質折疊需要在分子、原子的化學規則約束下，實現系統能量最小化，這是典型的優化難題。可人體卻能無時無刻、高效地完成蛋白質折疊，這是什么原因？

其實目前我們也沒有標準答案。一種推測是，生物演化讓自然界的蛋白質具備了特殊結構，人體接觸到的蛋白質種類有限，并非指數級數量，這類蛋白質本身就更容易實現能量最小化。

放到軟件工程、程序驗證與測試領域也是同理。我們通常會把需求校驗問題，轉化為布爾公式的可滿足性問題。這類實際場景生成的問題實例，本身帶有特殊結構，貪心策略或是其他精巧算法就能奏效。簡單來說，現實中遇到的實例，大多不是復雜度最高的最壞情況。

這樣的案例有很多，也有嚴謹的理論證明。比如求解線性規劃的單純形法，從理論上講，它面對最壞情況的不等式組時，復雜度是指數級的，但在實際應用中，運行效率接近線性。這是因為現實里的線性方程組都帶有額外結構，讓這套算法得以高效運行。如今學界雖然找到了能適配所有線性規劃問題的高效算法，但邏輯復雜，實際應用并不廣泛，單純形法反而因簡潔實用被沿用至今。

第三章：放寬正確性約束會怎樣

問：你剛才提到了蛋白質折疊問題，這類 NP 問題并沒有追求百分之百精準求解，而是給出結果并附上置信度，允許一定誤差。那么對于 P、NP 類問題，如果我們放寬絕對正確的要求，算法的漸進復雜度是否能擺脫指數級？

這是一個很有價值的思考。你提到的蛋白質折疊相關算法應該是AlphaFold阿爾法折疊，它依托現有蛋白質數據訓練而成，即便面對從未見過的蛋白質樣本，表現也十分出色。究其原因，還是因為現實中的蛋白質實例自帶特殊結構，能夠被高效求解。

當 NP 完全（即NPC）或 NP 難問題無法做到精準求解時，放寬要求、采用近似算法，是業界最常用的思路。我先明確概念：NP 完全問題是 NP 類中難度最高的問題，只要找到其中一個問題的高效解法，就能破解所有 NP 問題；反之，只要證明其中一個問題難解，就能證明全體 NP 問題難解。旅行商問題、能量最小化框架下的蛋白質折疊問題，都屬于 NP 完全問題。

既然這類問題不存在通用的精準高效算法，人們便轉而追求近似解：不要求結果達到理論最優，允許和最優值存在一定偏差，比如偏差比例控制在二分之一、百分之十以內。

NP 完全理論誕生于上世紀 70 年代初，而 90 年代出現的PCP 定理是一項重大突破。這一定理證明：即便是求解近似解，很多 NP 問題依舊難度極高。

舉個例子，布爾公式可滿足性問題：我們希望找到一組變量賦值，滿足全部約束條件。如果放棄百分之百滿足，改為滿足百分之九十的約束，難度是否會降低？答案是否定的。

以每個約束僅包含三個變量的情況為例：哪怕完全隨機賦值，也能滿足約八分之七的約束條件。而 PCP 定理，再結合赫斯塔德（Johan H?stad）的強化結論可以證明：只要你想在隨機猜測的基礎上，再多滿足哪怕極其微小的一部分約束，這個問題就會變回 NP 難問題。

也就是說，對于大量約束優化類 NP 問題，別說找到最優解，哪怕只是想得到一個 “比隨機猜測好一點點” 的近似解，難度都和求解最優解完全一致。

問：你介紹了 NP、NP 完全、NP 難這些復雜度類別，我了解到復雜度領域還有更多分類，能否整體介紹一下復雜度體系？

確實，計算復雜度領域有著龐大的分類體系，學界甚至專門搭建了 “復雜度動物園” 網站（ complexityzoo.net ），收錄了數百種復雜度類別，該網站由斯科特?阿倫森（Scott Aaronson）創立。

劃分復雜度類別的核心依據，是算法求解問題所消耗的資源量。

• P 類（多項式時間）：問題的求解時間，與輸入數據規模呈多項式關系。線性時間、二次時間、三次時間都屬于多項式時間，理論上都被視作高效算法。

• NP 類：不關注求解耗時，而是要求驗證答案的時間為多項式時間。

除了多項式時間、指數時間，還有雙重指數時間等更多時間復雜度劃分。

圖靈的經典理論早已證明：存在一部分問題，計算機根本無法求解，這類問題被稱為不可判定問題，這也是復雜度研究的起點。

時間只是其中一種資源。從理論和實際應用出發，我們還會考量其他資源：

1. 存儲空間：如何最小化計算過程占用的內存；

3. 通信開銷：多方協作計算時，數據交互的傳輸量（比如衛星通信，需要盡量減少通信次數與數據量）；

5. 能耗、并行計算能力：使用多臺計算機并行運算時，問題的提速上限。

復雜度理論的一大核心方向，就是根據資源消耗對問題分類，并研究不同復雜度類別、不同問題之間的關聯。

舉個例子：我們尚且無法判定所有 NP 完全問題的難易，但已經找到了它們之間高效的歸約方法。假設你掌握了解數獨的高效算法，就能通過歸約，將布爾可滿足性問題、旅行商問題、整數分解問題等，全部轉化為數獨問題求解，反之亦然。

因此，即便我們不清楚單個問題的復雜度，也能通過問題間的歸約關系，梳理出不同問題的難度層級。這些問題一部分源于現實技術約束，另一部分則來自純粹的數學探索。

第四章：NP 完全問題為何彼此等價

問：你提到所有 NP 完全問題都是等價的，如何將布爾可滿足性問題等價轉化為圖著色問題？這類轉化是通用邏輯，還是針對特定問題定制的？

這是一個很好的問題。不同 NP 完全問題之間的轉化，我們稱之為歸約算法。絕大多數歸約邏輯都比較簡單（PCP 定理相關的歸約除外，它的邏輯極為復雜），而且歸約是雙向成立的 —— 因為雙方都是 NP 完全問題。

最早被證明為 NP 完全的問題，就是布爾可滿足性問題，史蒂芬·庫克（Stephen Cook）和列昂尼德·萊文（Leonid Levin）在奠基性論文中，首次定義了NP 完全（即NPC，NP-Complete），并以它為范本展開證明。而所有其他 NP 問題，都可以歸約為布爾可滿足性問題，核心原因在于：計算本身具有局部性。

無論是筆記本還是其他計算設備，本質都是對二進制位做局部運算：讀取兩個寄存器的數據、做加法、異或、與運算等，通過一連串簡單的局部操作，最終得出結果。

計算過程中，設備的存儲狀態會逐步變化，而每一次狀態改變都只涉及局部數據。我們可以把整個計算流程，轉化為一系列約束條件，進而構建出布爾可滿足性問題。這也是絕大多數 NP 完全問題能夠互相歸約的根源。

我舉一個最簡單的例子：整數分解問題如何歸約為布爾可滿足性問題。如果有人給出了一個整數的因數，我們只需做乘法運算，就能驗證答案是否正確。乘法本身就是一套基礎的局部運算，我們可以把完整的乘法計算流程，拆解成一條條布爾約束。只要有人猜出因數（這正是 NP 問題 “給出答案即可驗證” 的特性），就能通過約束完成核驗。

同理，圖著色、數獨等問題，都可以依托 “局部約束” 這一特性，完成和布爾可滿足性問題的互相歸約。

第五章：時間復雜度與空間復雜度

問：剛才聊了時間復雜度和空間復雜度。在軟件工程中，我們常常需要在二者之間做取舍，目前有沒有成熟的理論，來解釋時空復雜度的權衡規律？

時空資源的權衡，是復雜度領域的經典研究方向，不同問題的表現也各不相同。部分問題存在明確的約束：比如某類運算的時間復雜度與空間復雜度的乘積，至少是輸入長度的平方。這類問題有兩種解法：一是使用極小的空間（對數空間），但要付出平方級的時間；二是采用線性時間運行，同時占用接近線性的空間。

不同計算模型下，這類時空權衡的結論也會存在差異。但有幾個普適性的經典結論：

1. 基礎規則：如果一個算法的運行時間為 t，那么它占用的存儲空間絕不會超過 t，因為計算機運行時不會訪問超出時長的存儲單元。

2. 五十年前，瓦連特（ Leslie Valiant ）、保羅（ Wolfgang Paul ）和 霍普克羅夫特（ John Hopcroft） 做出改進：運行時間為 t 的計算，可以轉化為存儲空間約為 t/log t 的等價計算。這套方案會大幅增加運行時間，但能節省空間。在很長一段時間里，學界都認為這就是時空優化的極限，并且在部分簡化計算模型中，也證明了無法再進一步優化。

而去年，瑞安?威廉姆斯（Ryan Williams）取得了重大突破：任意運行時間為 t 的計算，都可以改寫為僅占用√t 存儲空間的算法，空間壓縮幅度遠超以往。這套算法邏輯十分精巧，核心技術依托于史蒂夫?庫克（Stephen Cook，NP 完全理論奠基人之一）之子詹姆斯?庫克（James Cook），以及伊恩·默茨（Ian Mertz）此前的研究成果。當然，它的代價依舊是運行時間大幅增加，但也證明了時空復雜度之間，存在遠比想象復雜的關聯。

問：這套結論是針對圖靈機模型嗎？普通隨機訪問計算機是否適用？

這套理論很難用通俗語言拆解技術細節，我舉一個更早的經典案例，幫你理解 “極小空間完成復雜計算” 的神奇之處。

四十多年前，戴夫?巴林頓（David A. Mix Barrington）發現了一個有趣現象：多數判定問題（給定一串二進制數，判斷 0 多還是 1 多），常規思路需要對數空間來統計數量，這看起來是空間的下限。但他設計出一套算法，僅用常數空間就能解決這個問題。

前提是可以隨機讀取序列中任意位置的二進制位。這套算法的核心是非交換代數。簡單解釋：先后執行兩個操作，調換順序后結果會完全不同，這就是非交換性。比如先翻轉圖形、再旋轉，和先旋轉、再翻轉，最終形態不一樣。

巴林頓用五階置換（正五邊形的旋轉、翻轉操作）來編碼二進制位：讀到 1 就執行旋轉，讀到 0 就執行翻轉。整個過程只需要記錄正五邊形的形態，全程僅占用常數空間。而操作的非交換性，可以模擬出與門、或門等基礎邏輯運算。

這里有一個經典趣味謎題，可以直觀理解這個原理：有一幅畫，兩端系著繩子，墻面有兩顆釘子。要求把畫掛在兩顆釘子上，拔掉任意一顆釘子，畫都會掉落。如何纏繞繩子？這個謎題的解法，正是利用了操作的非交換性，和上述算法的底層邏輯相通。

雙釘掛畫謎題解法（拔任意一釘畫必掉）

圖源：顧森《浴缸里的驚嘆》人民郵電出版社

§1 幾何問題 第27題 插圖（作者妻子雪琴制作）

這個案例也能說明：很多看似需要大量空間的計算，都能借助特殊數學方法，在極小空間內完成。巴林頓的這項成果實用性極強，如今在密碼學領域有大量應用。而且這套算法的時間復雜度僅為平方級，效率很高。

問：你剛才提到，這套算法不需要記錄最終統計數值，只需要輸出 “0 更多” 或 “1 更多” 這類判斷結果。也就是說，只要是二值判定問題，無論輸入規模多大，都能依靠常數空間求解，對嗎？

沒錯。如果問題要求輸出完整的統計數字，就必須占用對應空間；但僅需給出 “是 / 否” 的判定結果，就可以借助這類方法突破常規空間限制。

第六章：為何業界廣泛使用可滿足性求解器

問：我們聊過 NP 完全問題彼此等價，我發現現實中很多工程師解決各類難題時，都會直接使用布爾可滿足性求解器。但問題轉化的過程會增大實例規模，按理說效率會降低，大家為何依舊選擇這種方式？

核心原因很簡單：多年來，學術界和產業界針對布爾可滿足性問題，研發了海量精巧的啟發式算法，專門適配現實場景中帶有特殊結構的實例。

這類啟發式算法不會盲目枚舉所有可能性，而是優先鎖定關鍵變量：部分變量一旦確定取值，會連帶約束大量其他變量，以此大幅壓縮檢索空間。

當然，在理論最壞情況下，這類優化毫無作用。學界也有相關猜想：布爾可滿足性問題的最壞復雜度，就是 2 的常數倍 n 次方，不存在指數級以下的通用解法。

但現實場景里，各類工程問題轉化而來的布爾公式，大多帶有天然結構，啟發式算法可以高效求解。除此之外，使用可滿足性求解器也十分便捷：程序、通信協議的合規性校驗，很容易轉化為布爾約束問題，這也是它在工程領域普及的重要原因。

第七章：隨機性也是一種計算資源

問：我們聊了算法用到的各類資源。你在講座中提出，隨機性也是算法的一種資源，這句話該如何理解？

隨機算法的應用由來已久，拋硬幣、統計抽樣都是利用隨機性。計算機普及后，人們發現引入隨機選擇，能極大提升各類計算的效率。

舉個經典例子：大數素性檢測。過去人們一直找不到高效的確定性算法，直到上世紀 70 年代，米勒（Miller）、拉賓（Rabin）等人提出了隨機素性檢測算法，完美解決了這個難題。

隨機算法的定義：算法運行過程中，可以做出隨機選擇。我們可以形象理解為設備內置了一枚公平硬幣，每次選擇都由拋硬幣決定。

但現實中，計算機并沒有真正的 “拋硬幣” 裝置，高質量的隨機數本身需要消耗資源（時間、硬件、算力）。目前獲取隨機數的常見方式分為幾類：

1. 采集物理噪聲：計算機熱噪聲、網絡流量、硬件傳感器數據等，這類隨機源成本低，但隨機性無法保證絕對均勻獨立；

2. 偽隨機數生成器：線性同余發生器、截取圓周率數位等，本質是確定性運算，只是結果看起來近似隨機；

3. 量子隨機源：利用光子自旋等量子現象，理論上能生成絕對均勻、相互獨立的隨機位，但硬件成本極高，且無法做到完美無瑕疵。

隨機算法普遍存在微小的出錯概率，這是和確定性算法最大的區別。因此，把隨機性視作一種計算資源，是復雜度理論里的標準視角：我們需要研究使用多少隨機位、隨機位的質量高低，才能在出錯率可控的前提下完成計算。

由此也衍生出一大研究方向：去隨機化，也就是盡量減少算法對真隨機數的依賴。理想狀態下，用少量真隨機位，通過確定性運算生成海量偽隨機序列，并且這些偽隨機序列，在對應算法中表現和真隨機序列毫無區別。

素性檢測算法的發展就是典型案例。高斯數百年前就提出了大數素性檢測的難題，長期以來，大家都依賴隨機算法，且無法減少隨機位的使用。直到 21 世紀初，阿格拉瓦爾（Agrawal）、卡亞爾（Kayal）和薩克塞納（Saxena），結合數論知識，分析了原有隨機算法對隨機性的使用邏輯，最終推導出AKS確定性素性檢測算法。

判斷隨機位質量的標準，本質就是偽隨機性的定義：一套偽隨機序列是否合格，不看它本身是否 “真隨機”，只看目標算法能否區分它和真隨機序列。

部分算法并不要求所有隨機位相互獨立，僅需要兩兩獨立、三三獨立即可。這類算法對隨機性的要求更低，只需極少量真隨機位，就能生成滿足條件的偽隨機序列。

我很認同一句話：隨機性的優劣，取決于觀測者，取決于觀測者的計算能力。我們不必糾結序列本身是否絕對隨機，只要運行算法的觀測者無法分辨真偽，這套偽隨機序列就完全可用。

第八章：隨機性依賴于觀測者的計算能力

問：你多次提到，隨機性由觀測者的計算能力決定，能否用通俗的例子解釋這一點？

這個例子來自曼紐爾?布魯姆（Manuel Blum）和西爾維奧?米卡利（Silvio Micali）的經典論文。

我們模擬一組實驗：我拋一枚硬幣，你來預測落地結果。

1. 無輔助工具：硬幣拋出后兩秒落地，你僅憑肉眼預判，猜對概率只有二分之一。對你而言，拋硬幣是完全隨機的，信息熵達到最大值；

2. 配備普通電腦：依舊來不及計算硬幣的運動軌跡，結果和第一種情況一致；

3. 連接超級計算機 + 高清傳感器、攝像頭：設備可以瞬間計算出硬幣的角動量、下落距離、空氣濕度等所有參數，精準預判落地正反面。此時對你而言，拋硬幣不再有隨機性，信息熵為零。

整個實驗中，拋硬幣這個物理事件本身沒有任何變化，唯一改變的，是觀測者的計算能力。

傳統數學、物理、哲學領域定義隨機性，都聚焦于事件本身；但復雜度理論視角完全不同：我們不關注事件，只關注觀測者與計算模型。一個事件是否隨機，完全取決于觀測者能否憑借自身算力預判結果。

這套理論是去隨機化研究的核心基礎。如果我們假設P 不等于 NP（或是存在其他高復雜度的難解問題），就能推導出一個重要結論：P 類問題等價于 BPP 類問題。(BBP，即Bounded-error Probabilistic Polynomial Time)

簡單解釋：所有存在高效隨機算法的問題，都一定存在對應的高效確定性算法。想要實現去隨機化，前提是存在算力無法破解的 “難解函數”。

這也引出了復雜度領域的核心范式：問題難度與隨機性相輔相成。二者的關聯是雙向的：一方面，問題存在計算難度，我們就能借此構造偽隨機序列、實現去隨機化；另一方面，如果我們成功實現了某類算法的去隨機化，也等價于證明了對應問題具備計算難度。

正因學界普遍相信 NP 問題難以求解，大家也傾向于認為：算法中使用的隨機性，大多可以被消除。

問：能否直觀解釋問題難度和隨機性的關聯？

可以。假設你是一臺算力有限的計算機（僅能運行多項式時間算法），面對旅行商這類難題，你無法直接得出答案，答案對你而言就存在不確定性，這就是信息熵。

我們需要借助技術手段放大這種不確定性：讓隨機生成的問題實例，對于多項式時間算力的觀測者而言，答案對錯的概率無限接近二分之一，觀測者哪怕比隨機猜測多贏一點點都做不到。這就是利用問題難度制造高質量隨機源。

基于這個思路，學界研發出了隨機放大技術。而偽隨機數生成器的邏輯恰好相反：用少量真隨機位（種子），生成海量偽隨機位，并且即便觀測者算力有限，也無法發現這些偽隨機位之間的關聯。

我和尼桑（Nisan）共同提出的 NW 偽隨機生成器，就是這類技術的代表。打個比方：攻克一個難解問題，就好比賺到第一筆一百萬；有了第一個一百萬，就能衍生出更多財富。同理，依托一個難解函數（第一份 “隨機性”），就能生成海量彼此無關聯的偽隨機序列。

問：回到你之前的觀點：如果擁有無限算力，世間就不存在真正的隨機事件，比如天氣、拋硬幣都能被精準預測。這個說法準確嗎？

從算法、計算的角度來看，這句話是成立的。擁有無限算力，就能輕松區分真隨機序列和低熵偽隨機序列。

但也要區分場景：如果我們的目標不是運行算法，而是純粹生成隨機事件（比如密碼、密鑰），規則就變了。香農信息論明確指出：密碼的安全性，完全取決于隨機源的信息熵。

這種場景下，我們要求事件本身的概率嚴格為二分之一，和觀測者的算力毫無關系。哪怕對方擁有無限算力，也無法改變事件本身的隨機屬性。這是信息論層面的硬性要求，和計算復雜度是兩個維度。

問：我還了解到，可以整合多個低質量隨機源，生成高質量隨機數，這是什么原理？

這屬于隨機提取 / 隨機提純理論，和偽隨機理論關聯緊密，但研究方向不同。

現實中我們很難獲取完美的真隨機源，天氣、量子現象、太陽黑子、股價走勢等，都屬于弱隨機源：它們存在一定不可預測性，但帶有偏差、關聯性，信息熵不足。

隨機提純的目標，就是對這類含部分信息熵的弱隨機序列做處理，提取出質量更高的隨機位。理論證明：無法用單個弱隨機源，提取出少量完美隨機序列，但可以生成多項式數量的輸出塊，其中99%以上都是完美隨機序列，僅有極少數存在缺陷。

使用時只需對所有輸出塊運行算法，再取結果的多數票，就能規避缺陷塊帶來的影響。這套理論體系已經發展得十分成熟，也衍生出多種不同前提條件下的實現方案。

問：你提到的二維數組、矩形圖示，大概率和和積定理有關，這是多弱隨機源提純的核心工具。

簡單講解和積定理：我們取一組整數，計算所有兩數之和，再計算所有兩數之積。如果一組數字求和后數量增長有限，那么求積后數量一定會大幅增加；反之，如果求積后增長有限，求和后必然大幅擴張。和與積兩種運算，具備 “互補” 特性。

在隨機提純中，我們將多個弱隨機源的輸出視作數字，混合使用加法與乘法運算。依托和積定理，就能保證輸出結果的多樣性大幅提升，也就是信息熵增加。這套方法可以逐步疊加，最終從多個弱隨機源中，提取出接近滿熵的高質量隨機序列。

需要說明的是，和積定理僅適用于多個相互獨立的弱隨機源，單個弱隨機源的提純，還需要依靠其他技術。

第九章：零知識證明及其意義

問：了解到你在零知識證明領域有深入研究，能否解釋什么是零知識證明，以及它的價值？

零知識證明（ZKP）如今已經走出理論圈，被大眾熟知。它的概念最早出自戈德瓦瑟（Shafi Goldwasser）、米卡利（Silvio Micali）和拉科夫（Charles Rackoff）的經典論文，這篇論文同時還定義了交互式證明。

傳統數學證明是書面形式，而交互式證明允許雙方實時對話，并且驗證方可以引入隨機選擇。證明者向驗證方論證一個命題，整個過程存在極小的誤判概率，而這個概率可以被無限壓低。

零知識證明，是交互式證明的特殊形式：證明者可以讓驗證方確信命題為真，但驗證方不會從交互過程中，獲得除 “命題為真” 之外的任何額外信息。

這個概念初聽十分反直覺：如何在不透露任何解題思路、答案細節的前提下，說服別人你掌握了正確解法？舉個例子：如果有人宣稱證明了 P 不等于 NP，并用零知識證明說服我，我最終只會確信這個結論成立，但完全無法知曉他的證明過程。

零知識證明的核心應用場景是密碼學。在各類密碼協議中，用戶需要使用私密信息完成運算，協議需要確保用戶沒有作弊，但又不能泄露隱私。

典型案例：公鑰密碼體系中，公鑰由兩個大質數相乘得到。我需要向對方證明：我給出的數字確實是兩個質數的乘積，但絕對不能泄露這兩個質數本身。零知識證明就能完美實現這一點。

后續我與奧德·戈爾德賴希（Oded Goldreich）、西爾維奧?米卡利（Silvio Micali）合作證明了一個重磅結論：零知識證明具備普適性。任何擁有傳統數學證明的命題，都可以構建對應的零知識交互式證明。無論是數學定理、密碼學命題，都能在保密核心信息的前提下完成論證。

問：它的底層原理是什么？比如把 P 對 NP 的證明轉化為零知識證明，具體如何實現？

首先需要一個基礎前提：單向函數存在。單向函數指正向計算簡單、逆向求解極難的函數，整數分解、離散對數都是公認的單向函數，整個密碼學體系都建立在這個假設之上。

依托單向函數，可以構建承諾方案：我擁有一個私密數字，對外公布一串看似隨機的公開數據。這串公開數據有兩個特性：第一，旁人無法反推出我的私密數字；第二，我事后也無法篡改最初的私密數字，相當于 “立下承諾”。兩個質數的乘積，就是最簡單的承諾方案實例。

我用三染色問題（經典 NP 完全問題）舉例，講解零知識證明的完整流程：命題：我們雙方都知曉一張圖，我宣稱可以用三種顏色給所有頂點染色，保證相鄰頂點顏色不同。我要在不透露具體染色方案的前提下，證明這個命題。

流程循環執行以下步驟：

1. 我為每個頂點的顏色生成一份承諾，對外公布，不直接展示顏色；

2. 你隨機挑選圖中的一條邊，要求我公開這條邊兩個頂點的承諾（解密）；

3. 你核驗：兩個顏色都屬于指定三色，且二者不相同。

你隨機挑選邊，就有概率抓到漏洞。反復執行上萬次后，我作弊卻不被發現的概率會指數級趨近于零。

零知識特性（不泄露答案）

如果我每次都使用同一套染色方案，多次核驗后你就能拼湊出完整方案。因此我每次都會隨機置換三種顏色的命名（紅、綠、藍重新分配）。

一張合法的染色方案，通過顏色置換能衍生出 6 種等價的合法方案。每次核驗相鄰兩個頂點時，你看到的都只是兩個隨機且不同的顏色，無法從中總結出任何有效信息。一輪交互結束，你一無所獲，自然也就無法還原完整染色方案。

依靠這套邏輯，我們就能為三染色問題構建零知識證明。

再結合 NP 完全問題的歸約特性：所有 NP 問題都可以轉化為三染色問題，并且原問題的 “證明 / 答案”，也會同步轉化為圖的合法染色方案。因此，只要三染色問題可以實現零知識證明，所有 NP 問題都能實現零知識證明。

補充一點：零知識證明并非絕對零誤差。如果命題本身為假，證明者僥幸蒙混過關的概率可以壓縮到無限小，但無法徹底降為零；如果命題為真，那么驗證結果絕對無誤。

第十章：量子計算帶來的變革

問：我們聊到了密碼學的單向函數，而量子計算的出現，極大改變了復雜度理論。你如何看待量子計算對整個領域的影響？

量子力學是描述客觀世界的基礎理論，學界自然會思考：能否讓計算機遵循量子力學規則運行？

量子計算機依托量子疊加態和幺正變換工作，和經典計算機、隨機計算機有本質區別。量子世界存在干涉效應，可以理解為 “概率能夠相互抵消”，運算邏輯遠超傳統概率范疇。

從計算模型層級來看：量子計算機的能力，至少強于所有經典隨機計算機。因為對量子比特做測量，本身就能得到真隨機位。

量子計算的概念在上世紀 80 年代由費曼等人提出，最初目的是模擬復雜的量子物理系統。很長一段時間里，量子算法只存在于理論模型中，無法解決現實中的經典難題。

1994 年，彼得?肖爾（Peter Williston Shor）取得顛覆性突破：他設計出量子算法，可以在多項式時間內完成整數分解和離散對數求解。而這兩個問題，正是現有公鑰密碼體系的安全根基。這個結果震驚了整個學界和產業界。

自此之后，各國政府、企業投入巨額資金研發量子計算機。但量子計算的落地面臨巨大技術難題：

1. 量子疊加態極其脆弱，外界環境的微小干擾都會破壞計算狀態，遠不如經典硬件穩定；
2. 
   
3. 量子糾錯碼可以緩解噪聲問題，但也只是解決方案之一，硬件層面依舊存在大量待攻克的技術壁壘。

量子計算的崛起，也倒逼密碼學完成全面革新：

如果未來有人研發出經典多項式時間整數分解算法，現有金融、互聯網的安全體系都會徹底崩潰。而肖爾算法證明，成熟的量子計算機可以直接破解現有主流公鑰密碼。

因此，當下密碼學的核心目標，是尋找連量子計算機也難以求解的數學難題，搭建抗量子攻擊的新密碼體系。

單向函數在自然界中十分普遍（比如雞蛋做成煎蛋無法逆向復原），但能構建公鑰體系的陷門單向函數十分稀少。繼整數分解、離散對數之后，格密碼、帶誤差學習問題，成為抗量子密碼的主流候選方案。截至目前，學界依舊沒有找到破解這類問題的高效量子算法。

量子計算還讓計算機科學、物理學深度融合：算法思想開始應用于量子引力、黑洞等前沿物理研究；同時物理領域的新發現，也反哺計算模型與復雜度類別。

還有一項極具顛覆性的理論成果：多年前學界證明了MIP*=RE。

簡單解釋：引入量子證明者、量子糾纏的交互式證明系統，可以讓經典意義上不可計算、不可判定的問題，被高效驗證。

這個結論看似脫離現實，卻衍生出全新的數學工具，成功解決了數學、物理領域多個懸而未決的經典猜想。這套理論誕生于復雜度學者構建的抽象模型，最終卻成為攻克硬核難題的利器，這也是計算理論最迷人的地方之一。

這類長達兩百頁的復雜論文，結論又十分顛覆，學界要如何核驗其正確性？

這是所有高深數學成果都會遇到的問題。P 與 NP、黎曼猜想時常出現各種 “證明版本”，很多都需要漫長時間核驗、推翻。克萊數學研究所的千禧年難題之一 —— 龐加萊猜想，其證明也耗費了數年時間梳理細節、修正漏洞。

MIP*=RE 的原始論文確實存在小漏洞，不過很快就被修復。在數學領域，理論的真偽本身就是學術界集體論證、達成共識的過程。如今形式化證明工具（比如 Lean）逐步成熟，未來復雜證明的核驗，也會變得更加規范。

第十一章：數學與計算機科學的關系

問：你的研究兼具計算機科學與數學屬性，在你看來，二者之間是什么關系？

我所研究的復雜度理論、算法理論，是站在數學與計算機科學交叉地帶的學科。一方面，我們的產出是標準的數學定理與嚴格證明，和代數、分析、拓撲等純數學分支別無二致；另一方面，我們的研究問題、模型，全都圍繞計算展開。

計算無處不在：代碼運行、蛋白質合成、生物繁衍、天氣演變，本質都是一系列基礎局部操作的連續演化。我們研究計算，核心是分析計算過程消耗的各類資源，理解自然現象背后的運算邏輯。

這個交叉領域能同時吸收兩方面的養分：工業界、硬件系統為我們提供現實問題；純數學為我們提供嚴謹的推理工具。我們構建模型、定義概念，有時是為了解決實際問題，有時純粹是出于理論探索的審美與興趣。

很多人認為理論計算機科學是 “為了做題而做題”，但我做研究從來不以應用為首要目標。支撐我數十年深耕這個領域的動力是什么？

首先要厘清一點：我們做的核心工作，是構建模型，而非單純解題。提出新定義、搭建新模型，是這個領域的核心，這一點甚至比傳統數學更加突出。比如我們重新定義的 “隨機性”，就衍生出大量顛覆性結論。

我本科、研究生、博士后階段都深耕計算機科學，這讓我對 “計算” 本身抱有天然的興趣。隨著領域發展，計算理論已經滲透到物理、生物等所有學科，成為理解世界的基礎視角，這本身就極具吸引力。

從業四十五年，我見證了理論成果不斷落地：零知識證明最初被我認為落地成本極高，幾乎不會被實際應用，但如今它在區塊鏈、隱私計算等領域大放異彩；PCP 定理重塑了編碼理論；密碼學、量子算法更是深刻改變了整個科技行業。

當然，領域內也存在大量短期內看不到落地價值的問題，P 與 NP 就是典型。我們至今都無法證明基礎結論，甚至連 “乘法比加法更難” 這種簡單猜想都無法證實。但研究這些問題，是為了探索計算能力的邊界：什么能算、什么不能算，資源該如何取舍，不同問題之間存在怎樣的關聯。

目前人類對于 “計算” 的理解，依舊處于初級階段。哪怕研究成果暫時無法落地，探索本身也具備獨一無二的價值。

這個領域的科研日常和工程崗位截然不同：工程師每年都能產出落地項目，但理論研究者絕大多數時間都在不斷試錯、思考，一整天毫無進展是常態。但試錯的過程并非毫無意義，很多靈感都會在反復失敗中慢慢積累。只有真正享受思考、享受探索的人，才能堅持下來。

第十二章：科研生涯中的重大突破

問：理論領域的重大突破往往間隔數十年。當你取得里程碑式的研究成果時，內心是怎樣的感受？

取得重大發現的時刻，自然會感到欣喜，但這類機遇十分稀少。

整個科學領域的進步，更像螞蟻搬家：成千上萬的研究者，每年產出海量論文，絕大多數成果都是微小的改進 —— 優化一個邊界、改良一種技巧、補充一個案例。這些細碎的進展看似不起眼，卻是整個領域向前推進的基石。

真正顛覆性的成果可遇不可求。就像巴林頓發明常數空間計數算法時，他最初的目標其實是證明 “這件事不可能完成”，最終卻意外得到了相反的結論。這種突破固有認知的發現，會給研究者帶來極大的震撼。

我常對學生和博士后說：不要為了百萬美元獎金去研究千禧年難題。投身這個領域，核心是享受思考的過程。

日復一日的試錯確實枯燥，但每一次微小的收獲，都會帶來滿足感。這也是理論研究獨有的魅力。

第十三章：給年輕時的自己的建議

問：最后一個問題。以你多年的經驗，如果回到職業生涯起點，你會對當初剛入行的自己提什么建議？

我很幸運，一路走來沒有想要改變的選擇。這個領域對年輕人十分友好，沒有森嚴的等級，學術會議上，新人也能和頂尖學者平等交流。我求學時遇到了優秀的導師，職業生涯中也結識了無數出色的合作伙伴。

如果一定要給出一條通用建議，那就是：在職業生涯早期，去研究自己真正熱愛的問題。

初入科研領域時，要多嘗試不同方向，閱讀不同領域的論文，接觸不同類型的問題，摸索自己的天賦與興趣所在。多數情況下，你最熱愛的方向，也正是你最擅長的領域。

第十四章：結束語

非常感謝你抽出時間接受本次訪談。

感謝各位觀看本期播客。如果喜歡本期內容，歡迎點贊、留言支持。大家有想要邀請的嘉賓，也可以在評論區推薦，往期多位嘉賓都是來自觀眾的提議。

除了播客之外，我目前在研發一款人體工學分體鍵盤，原型機已經完成，并在眾籌平臺上線，上線八小時就達成了眾籌目標。感謝所有第一批支持的朋友。目前團隊正在推進模具生產，眾籌通道依舊開放，鏈接我會放在簡介中。

再次感謝大家的觀看，我們下期再見。

參考資料

https://www.youtube.com/watch?v=5GUcvSAJcJw

https://www.quantamagazine.org/for-algorithms-a-little-memory-outweighs-a-lot-of-time-20250521/

https://complexityzoo.net

閱讀最新前沿科技趨勢報告，請訪問21世紀關鍵技術研究院的“未來知識庫”

未來知識庫是 “21世紀關鍵技術研究院”建 立的在線知識庫平臺，收藏的資料范圍包括人工智能、腦科學、互聯網、超級智能，數智大腦、能源、軍事、經濟、人類風險等等領域的前沿進展與未來趨勢。目前擁有超過8000篇重要資料。每周更新不少于100篇世界范圍最新研究資料。 歡迎掃描二維碼或訪問https://wx.zsxq.com/group/454854145828進入。

截止到2月28日 ”未來知識庫”精選的百部前沿科技趨勢報告

（加入未來知識庫，全部資料免費閱讀和下載）