Avi Wigderson：他用数学之美揭示计算的本质，从随机性到交互证明，从复杂度到密码学，编织出一张理论计算的宏大图景

图灵奖第五十八届（2023）| Avi Wigderson：他用数学之美揭示计算的本质，从随机性到交互证明，从复杂度到密码学，编织出一张理论计算的宏大图景

一句话概括：当计算机科学家还在研究”具体算法”时，Wigderson思考的是”计算的根本限制”——证明随机性可以被确定性模拟（伪随机数生成器）、交互证明系统比非交互强大（零知识证明）、复杂度类之间有意想不到的联系（PCP定理）。他让计算复杂性理论从抽象的数学游戏变成密码学、算法设计、量子计算的理论基础，让我们理解”什么问题可解、什么问题难解”的深刻原因。

🏆 获奖简介

Avi Wigderson（阿维·威格德森，1956-）是计算复杂性理论的领军人物，随机性与计算理论的先驱，理论计算机科学的集大成者。

个人信息：

出生时间：1956年9月9日
出生地点：以色列海法
主要成就：
- 伪随机数生成器理论（Nisan-Wigderson生成器）
- 交互证明系统与零知识证明（GoldwasserMicali-Wigderson协议）
- PCP定理（概率可检验证明）的基础工作
- 扩展图（Expander Graphs）的构造与应用
- 复杂度类分隔的突破性工作
荣誉：
- 内文林纳奖（Nevanlinna Prize，1994）
- 哥德尔奖（Gödel Prize，多次）
- 阿贝尔奖（Abel Prize，2021）
- 图灵奖（2023）

教育背景：

1977年：以色列理工学院（Technion）计算机科学学士
1980年：普林斯顿大学计算机科学硕士
1983年：普林斯顿大学计算机科学博士（导师：Richard Lipton）

职业经历：

1983-1986年：加州大学伯克利分校博士后
1986-1999年：普林斯顿大学教授
1999-至今：普林斯顿高等研究院（IAS）教授
获奖年份：2023年
获奖原因：在计算理论领域的基础性贡献，包括对随机性在计算中作用的核心认识、复杂性理论以及密码学

为什么他是第五十八位？ 1980年代，计算机科学面临根本问题：P是否等于NP？随机算法为何有效？密码学的安全基础何在？Wigderson以数学家的深度和计算机科学家的直觉，在这些前沿问题上做出一系列突破。他证明伪随机性可从弱假设构造（Nisan-Wigderson），让随机算法理论站在坚实基础上；他与Goldwasser、Micali发明零知识证明，让密码学从工程技巧升华为数学理论；他贡献PCP定理，揭示近似算法的根本困难；他构造扩展图，连接图论、组合学与计算。从算法设计到密码协议，从量子计算到机器学习，Wigderson的思想渗透到理论计算机科学的每个角落。他让”计算复杂性”从象牙塔的智力游戏变成理解计算本质、设计实用系统的理论基石。

🚀 主要贡献

1. 伪随机数生成器：用确定性模拟随机性

背景（1980年代）：

随机算法的困境：
- 许多算法依赖随机数（如快速排序的随机pivot、Miller-Rabin素性测试）
- 真随机数难以获取（硬件随机源昂贵）
- 伪随机数生成器（PRNG）是否”足够好”？

核心问题：

能否用确定性算法生成”看起来随机”的比特串，骗过所有高效算法？

Nisan-Wigderson生成器（1994）：

思想：

种子：短随机串（如log n位）
扩展：生成多项式长的伪随机串（如n位）
安全性：基于计算困难性假设

构造（简化）：

输入：d位种子 s
假设：存在函数f困难计算（需要2^d时间）

算法：
1. 选择组合设计D = {S₁, S₂, ..., Sₘ}（每个Sᵢ是{1,...,d}的子集）
2. 对每个Sᵢ：
   输出 f(s限制到Sᵢ的位)
3. 输出m位伪随机串

关键性质：

拉伸：d位种子 → m位输出（m ≫ d）
安全性：如果f难以计算，则输出对多项式时间算法”看起来随机”
可去随机化：BPP ⊆ P假设下（存在强困难函数），所有概率算法可去随机化

理论意义：

复杂度类连接：BPP（概率多项式时间）= P（确定性多项式时间）在合理假设下
哲学含义：随机性不是”额外资源”，而是可以用复杂度交换

实践意义：

密码学PRNG：从短密钥扩展为长密钥流（如AES-CTR模式）
蒙特卡洛方法：用伪随机数代替真随机

2. 零知识证明：证明而不泄露知识

背景（1985年）：

密码学挑战：如何证明”我知道某个秘密”而不泄露任何信息？
例子：
- 证明”我知道图的哈密尔顿回路”而不显示回路
- 证明”我知道密码”而不传输密码

零知识证明的发明（Goldwasser-Micali-Wigderson, 1985）：

三色图问题示例：

问题：

给定图G，我声称有3-着色（相邻顶点颜色不同）
如何证明而不泄露具体着色？

协议：

证明者P（知道3-着色）与验证者V（怀疑者）

重复多轮：
  1. P随机排列3种颜色（如红→绿，绿→蓝，蓝→红）
  2. P对每个顶点"盖住"颜色（承诺方案）
  3. V随机选择一条边(u,v)
  4. P揭示u和v的颜色
  5. V检查：两颜色不同？

如果P真知道着色：
  - V看到的每对颜色都不同（接受）
如果P在骗：
  - 至少有一边两端同色，重复k轮后被抓住概率 → 1 - (1/E)^k

零知识性质：

完备性：真实证明者总能让验证者相信
可靠性：撒谎者几乎肯定被揭穿
零知识：验证者除了”命题为真”外，学不到任何信息（通过模拟器证明）

GoldwasserMicali-Wigderson协议（GMW，1986）：

成就：

证明所有NP问题都有零知识证明
如果存在单向函数（One-Way Function），则构造适用

影响：

密码协议：
- 身份认证：无需传输密码
- 多方安全计算：各方不泄露输入，共同计算结果
区块链：
- zk-SNARK（简洁非交互零知识论证）
- Zcash隐私币：证明交易合法而不泄露金额

3. 交互证明系统：IP = PSPACE

突破（Lund-Fortnow-Karloff-Nisan + Shamir, 1990-1992）： Wigderson在IP理论早期工作奠定基础

经典结果：

IP = PSPACE

即：交互证明能高效验证的问题类 = 多项式空间可解问题类

意义：

之前认为：NP是”可高效验证”的极限
现在发现：加上交互，验证能力大幅提升
哲学：交互比独白强大

例子：

图非同构：证明两个图不同构（属于IP但不知是否在NP）
多项式恒等式：检验两多项式是否相等

应用：

PCP定理（下文）
量子交互证明（QIP = PSPACE）

4. PCP定理：近似算法的困难根源

PCP（Probabilistically Checkable Proofs，概率可检验证明）

定理（Arora-Safra, 1992；Arora-Lund-Motwani-Sudan-Szegedy, 1998）：

NP = PCP(log n, O(1))

含义：

对于任何NP问题，存在证明格式：
- 证明长度：多项式
- 随机性：O(log n)个随机位
- 查询：只读O(1)个证明位
- 准确性：
  - 真命题：总被接受
  - 假命题：至少一半概率被拒绝

Wigderson的贡献：

与Arora等合作的PCP定理证明
长码（Long Code）的引入

近似算法的硬度： PCP定理推出：

Max-3SAT：找最优解NP难，找1.0001近似解也NP难
TSP：旅行商问题近似到任意常数因子，除非P=NP

影响：

算法设计：明确哪些问题”近似也难”
理论基础：唯一游戏猜想（Unique Games Conjecture）研究

5. 扩展图：连接性与随机性的桥梁

扩展图定义：图G=(V, E)是(n, d, λ)-扩展图如果：

n个顶点，度数d（正则图）
扩展性：第二大特征值λ远小于d（即λ/d → 0）

性质：

高连通性：任何小点集有很多边连到外部
伪随机性：随机游走快速混合
编码：纠错码构造

Wigderson贡献：

构造方法：代数几何、组合方法
应用：
- 网络拓扑设计（高鲁棒性）
- 去随机化算法
- 复杂度下界证明

实际应用：

数据中心网络：Clos网络、Fat-Tree
纠错码：LDPC码（Low-Density Parity-Check）
图算法：近似最大割、谱聚类

6. 复杂度类的分隔

Wigderson的工作（多篇论文）：

非一致计算（电路复杂度）：

下界证明：某些函数需要大电路
自然证明（Natural Proofs）困境：Razborov-Rudich障碍
Wigderson贡献：限定模型下的突破

矩阵乘法的复杂度：

与他人合作研究矩阵乘法的算术电路复杂度
连接到代数几何的秩界

通信复杂度：

多方计算的通信下界
应用到数据流算法

7. 计算与数学的统一

跨学科贡献：

代数几何 → 计算：代数证明系统、纠错码
数论 → 密码学：原根、离散对数
拓扑 → 算法：同调计算的复杂度

哲学：

“计算是数学的新视角，数学是计算的语言。”

著作：

《数学与计算》（Mathematics and Computation, 2019）：
- 面向数学家的计算理论
- 统一视角：复杂度、随机性、交互

🌍 对世界的深远影响

密码学的数学基础

零知识证明的应用：

区块链隐私：Zcash、Monero
匿名凭证：证明”我满18岁”而不泄露生日
安全多方计算：金融机构共同反洗钱而不共享客户数据

伪随机数生成器：

TLS/SSL：网页加密使用PRG从握手密钥扩展会话密钥
密码流算法：AES-CTR、ChaCha20
区块链：共识算法的随机性来源

算法设计的指导原则

去随机化：

实践：许多”随机”算法实际用确定性实现（伪随机）
理论保证：Wigderson的理论确保这样做是安全的

近似算法的极限：

PCP定理告诉我们：哪些问题”再努力也没用”
资源分配：避免在无望的问题上浪费时间

量子计算的理论基础

Wigderson对量子复杂度的贡献：

量子交互证明（QIP）：QIP = PSPACE
量子伪随机性：量子态的伪随机生成

影响：

量子算法（Shor、Grover）的复杂度分析
量子密码协议的安全性证明

机器学习的理论透镜

计算学习理论（Valiant的PAC学习）：

Wigderson扩展到分布式学习、在线学习
差分隐私：如何在学习的同时保护隐私（与伪随机性相关）

深度学习的复杂度：

神经网络的表达能力（电路复杂度视角）
梯度下降为何有效（伪随机景观）

🏆 获奖理由（通俗版）

ACM官方表彰：“在计算理论领域的基础性贡献，包括重塑我们对随机性在计算中作用的理解、计算复杂性以及密码学。”

更通俗的理解：

Avi Wigderson证明：

随机性不是魔法：看似需要”随机”的算法，其实可以用”伪随机”模拟，而伪随机来自困难问题
交互比独白强大：证明者和验证者对话，能验证比传统证明更多的命题（IP = PSPACE）
近似也有极限：不是所有难题都能”差不多解决”，PCP定理揭示近似算法的根本障碍

他让计算复杂性理论从”什么能算、什么不能算”扩展到”什么能快速算、什么只能慢速算、什么连近似都难”，为算法设计、密码学、量子计算提供理论罗盘。

👤 个人生平与传奇

成长经历

童年（1956-1970年代）：

以色列海法：数学天赋早现
军队服役：以色列全民义务兵役
理工学院（Technion）：本科，计算机科学

普林斯顿博士（1980-1983）：

导师：Richard Lipton（复杂度理论大师）
论文：图的色数与完美图
氛围：1980年代普林斯顿理论计算的黄金时代

学术生涯

伯克利博士后（1983-1986）：

合作：Manuel Blum（1995图灵奖）、Shafi Goldwasser（2012图灵奖）
零知识证明的诞生：GMW协议

普林斯顿教授（1986-1999）：

学生：培养大批理论计算机科学家
合作：Noam Nisan（伪随机数）、Sanjeev Arora（PCP）

高等研究院（1999-至今）：

职位：Herbert H. Maass Professor
环境：爱因斯坦曾工作的地方，纯理论研究
自由：无教学负担，专注研究

性格与风格

深刻且广博：

不满足于解决单个问题，追求统一理论
连接看似无关的领域（图论、代数、复杂度）

慷慨的合作者：

与数百位学者合作（论文合著者超过200人）
推广”开放问题文化”：公开分享未解问题

热情的教育者：

虽在高等研究院无教学义务，仍经常讲课
著作《数学与计算》：面向数学家的复杂度理论

荣誉

重大奖项：

内文林纳奖（1994）：信息科学领域的”小图灵奖”
哥德尔奖（多次）：理论计算机科学最佳论文
阿贝尔奖（2021）：数学界最高荣誉之一，与Lovász共享
图灵奖（2023）

象征意义：同时获阿贝尔奖（数学）和图灵奖（计算机）：体现计算与数学的深度融合。

💭 为什么他值得纪念？

1. 他重新定义了”随机性”

之前：

随机算法是”魔法”：不知为何有效，但确实有效
真随机数 vs 伪随机数：概念模糊

之后：

伪随机性有严格数学定义（通过计算不可区分性）
基于困难问题的PRG：随机性 = 复杂度的另一面
BPP = P（在合理假设下）：随机不是额外能力

启示：计算机科学的核心不是”计算什么”，而是”资源（时间、空间、随机）如何转换”。

2. 他证明了”交互”的力量

零知识证明：

改变密码学：从”隐藏信息”到”证明知识”
影响区块链：隐私与透明的平衡

交互证明系统：

IP = PSPACE：交互扩展验证能力
哲学：对话（interactive）比讲座（non-interactive）强大

3. 他连接了理论与实践

常见误解： “复杂度理论是纯数学，与实际无关”

Wigderson的反驳：

密码学：零知识证明 → Zcash、TLS
算法：伪随机数 → 所有随机算法的实现
硬件：扩展图 → 数据中心网络设计

事实：他的理论工作，10-20年后变成工程实践。

4. 他示范了”数学家的计算机科学”

风格：

深刻的数学证明（代数几何、概率论、拓扑）
计算的直觉（算法、复杂度类）
统一的视角（《数学与计算》）

对比：

工程导向：Knuth、Aho（算法实现）
数学导向：Wigderson、Lovász（计算本质）
两者都重要，Wigderson证明”数学也能改变计算”

🔍 技术深度：零知识证明的数学

模拟器的概念

零知识的形式化定义：对于协议(P, V)（证明者Prover、验证者Verifier）：

完备性：P和V诚实交互，V总接受真命题
可靠性：欺骗者P*不能让V接受假命题（除非小概率）
零知识性：存在模拟器M，M(x)的输出与V看到的交互记录不可区分

模拟器M做什么？

输入：公开信息x（如”图G有3-着色”）
输出：虚假交互记录（看起来像真实协议运行）
关键：M不知道秘密（如具体着色），但仍能”伪造”记录

直觉：如果V能从交互中学到秘密，则模拟器M无法不知秘密还伪造记录。因此，V学不到秘密 → 零知识。

例子：图3-着色的完整协议

承诺方案（Commitment Scheme）：

绑定性：P提交后不能修改
隐藏性：V看不到内容

协议（第i轮）：

1. P选择随机排列π：{红,绿,蓝} → {1,2,3}
2. 对每个顶点v：
   P计算承诺c_v = Commit(π(color(v)), r_v)  // r_v是随机数
   发送所有c_v给V
3. V随机选择边(u, w)
4. P揭示：
   π(color(u)), r_u
   π(color(w)), r_w
5. V验证：
   - 承诺正确？
   - π(color(u)) ≠ π(color(w))？
   如果是，接受本轮；否则拒绝

零知识分析：

V看到什么？
- 每轮：一条边的两端点有不同颜色（{1,2}或{1,3}或{2,3}）
- 但颜色被随机排列打乱，V学不到原始着色
模拟器M：
- 不知道着色，但知道V会选哪条边（假设V是确定性）
- M”猜测”V的选择，只承诺该边两端，其他随机
- 如果猜对：输出看起来真实
- 如果猜错：重来（M可以”倒带”）
不可区分性：真实交互 vs 模拟输出，V无法区分

🧪 实践意义：零知识证明的应用

Zcash：隐私加密货币

问题：

Bitcoin透明：所有交易公开（地址、金额）
隐私需求：企业、个人不愿公开财务

Zcash方案（基于zk-SNARK）：

隐藏：发送方、接收方、金额
证明：仍能验证交易合法（余额足够、无双花）
如何？
- 零知识证明：“我的交易满足规则”
- 验证者：矿工/节点检查证明，无需知道具体内容

技术：

zk-SNARK：简洁非交互零知识论证
- 简洁：证明小（几百字节）
- 非交互：无需多轮对话（用公共参考串CRS）

身份认证：Fiat-Shamir协议

传统方法：

发送密码 → 被窃听风险

零知识方法（基于离散对数）：

设置：
  - 公开：大素数p、生成元g、公钥y = g^x mod p
  - 秘密：私钥x

协议（证明"我知道x"）：
1. P选择随机r，计算t = g^r mod p，发送t
2. V发送随机挑战c
3. P计算s = r + cx mod (p-1)，发送s
4. V验证：g^s ≟ t × y^c mod p

零知识：
  - V只看到(t, c, s)
  - 模拟器：随机选c、s，计算t = g^s / y^c
  - 与真实交互不可区分

安全多方计算：Yao的百万富翁问题

问题： Alice和Bob想知道谁更富，但不愿透露财富值。

零知识解决（简化）：

Alice和Bob运行协议
输出：Alice更富 / Bob更富
保证：
- 除了比较结果，互相学不到财富具体值
- 基于零知识证明每一步计算正确

应用：

金融机构联合反欺诈（不共享客户数据）
医疗数据分析（保护隐私）

📚 延伸阅读

书籍

Wigderson: “Mathematics and Computation” (2019)
- 综合性著作，面向数学家的计算理论
Goldreich: “Foundations of Cryptography” (2001)
- 零知识证明的严格处理
Arora-Barak: “Computational Complexity: A Modern Approach” (2009)
- 复杂度理论教材，涵盖PCP、伪随机性

论文

Goldwasser-Micali-Wigderson: “Proofs that Yield Nothing but Their Validity” (1985)
- 零知识证明的原始论文
Nisan-Wigderson: “Hardness vs. Randomness” (1994)
- 伪随机数生成器理论
Arora-Safra: “Probabilistic Checking of Proofs” (1998)
- PCP定理

在线资源

Wigderson主页（IAS）：论文、演讲视频
Complexity Zoo（复杂度类百科）
Simons Institute视频：最新研究报告

🌟 精神遗产

”数学与计算是一体的”

Wigderson的哲学：

“计算不是数学的’应用’，而是数学的新视角。”

体现：

阿贝尔奖（数学）+ 图灵奖（计算）
代数几何 → 纠错码、零知识证明
概率论 → 伪随机性、PCP

”理论今天，实践明天”

历史：

1985年：零知识证明（纯理论）
2020年：Zcash、Filecoin（区块链应用）
时间差：35年

教训：

基础理论投资值得
“无用”理论可能成为未来关键技术

”开放问题是礼物”

Wigderson的习惯：

公开分享未解问题列表
鼓励年轻学者攻克

文化：

理论计算社区的”开放问题会议”
对比商业界的”专利保护”

总结语： Avi Wigderson是计算复杂性理论的诗人——他不满足于解决具体问题，而是追寻计算的本质规律。从证明伪随机性可从困难问题构造，到发明零知识证明让密码学从工程升华为数学，从PCP定理揭示近似算法的根本障碍，到扩展图连接图论与复杂度，他编织出一张理论计算的宏大图景。

他的工作证明：理论不是与实践脱节的象牙塔，而是未来技术的预言。今天的区块链隐私协议、加密货币、安全多方计算，都建立在他35年前奠定的数学基础上。他同时获得数学界的阿贝尔奖和计算机界的图灵奖，象征着两个学科的深度融合——计算是数学的新语言，数学是理解计算本质的钥匙。

这束始于1980年代普林斯顿的复杂度研究之光，至今仍在照亮密码学、量子计算、机器学习的理论前沿，并将继续指引我们理解”什么可计算、什么难计算、什么不可计算”的永恒问题。Wigderson提醒我们：在这个算法驱动的时代，最实用的知识往往来自最抽象的数学。

最后更新: 2024年12月 本文为图灵奖系列文章,旨在以通俗方式介绍计算机科学先驱的贡献