2023 Avi Wigderson —— 計算的深淵與隨機性的價值#
「P vs NP 未解，他卻拿了圖靈獎。方法：不問『能不能解』， 改問一個更精緻的問題——隨機性、零知識、密碼學， 到底能買到多少計算能力？」
案件檔案#
| 項目 | 內容 |
|---|---|
| 得主 | Avi Wigderson (1956–) |
| 得獎理由 | 理論計算機科學的貢獻，特別是複雜度理論 |
| 關鍵詞 | 去隨機化、零知識、計算複雜度、放大定理 |
前因#
1980s 的謎團連環：
- 隨機演算法（1976 Rabin 案）威力驚人——真隨機 是必需品嗎？（硬體難給，哲學可疑）
- 互動證明（2012 案）與密碼學需要「難題」作地基， 但 P vs NP 未解——能否在未證明的地基上蓋樓？ （可以：單向函數假設）
Wigderson 在普林斯頓高等研究院（IAS）成為這些謎題的 中央情報局局長。
線索與推理#
線索一：去隨機化（1990s，與 Impagliazzo 等的譜系）#
Hardness vs Randomness 范式：
若存在難以計算的函數 f（電路下界），
則 f 可作偽隨機生成器：
PRG(seed) → 輸出與真隨機不可區分（2012 案語言）
⟹ BPP = P（若強下界成立）
「隨機性 = 難度的另一面」——兩者可互相兌換
Wigderson–Zuckerman：放寬假設下的放鬆版（derandomize AM 等）
哲學結論：隨機的計算能力可以「用難度偽造」—— 2024 年他的新突破（與 Chen、Karlin 等）證明 BPP = P 無需任何未證假設以外的條件？ 不—— 2024 年結果：BPP 對的 NEXP 型去隨機化的最後拼圖 （derandomizing BPP with optimal hardness）仍在推進； 但「hardness⇒randomness」已是公認主幹。
線索二：零知識的放大（1988，與 Goldreich、Oren）#
零知識（2012 案）原本只是「對誠實多數」的性質
Wigderson 等：任何 NP 語言都有零知識證明
（以位元承諾為磚）
且零知識可在並行/多證明者下放大——
通往 MIP = NEXP（Babai–Fortnow–Lund–Wigderson 1991）
線索三：計算複雜度的全景著作#
《Mathematics and Computation》（2019）：把複雜度 理論寫成數學共同體的入門書；P vs NP 的認識論： 我們甚至無法證明「無法證明」（自然證明障礙、 relativization 障礙）——他是最清晰的地圖繪製者。
線索四：譜系經營#
IAS 的交叉培訓（IMPAN、暑期學校）、指導數十位 複雜度學者；2021 年阿貝爾獎 + 2023 圖靈獎—— 兩大獎證明理論計算機科學已是數學的正統分支。
理論評析#
Wigderson 的方法論：把資源視為可交易的貨幣。
隨機位元 ←→ 計算難度 （hardness vs randomness）
互動輪數 ←→ 證明長度 （IP = PSPACE）
多個證明者 ←→ 單個證明者 （MIP = NEXP）
知識洩漏 ←→ 通信量 （零知識壓縮）
每一行都是一條「匯率定理」——資源等價理論是他 四十年的單一母題。
後果#
- 密碼學的「假設—構造」經濟學有了地圖（什麼假設 買什麼功能）。
- 去隨機化思想影響 SAT 求解器、密碼 PRG 與 資料結構的下界研究。
關聯案件#
→ 1985-Richard-Karp與NP完全問題的證明、2012-Goldwasser-Micali與零知識證明、2000-Andrew-Yao與偽隨機性及複雜度理論