Avi Wigderson 是历史上唯一一位同时获得图灵奖（计算机科学）和阿贝尔奖（数学）的人。

他最近上了一次播客访谈。谈到

• 他对 P vs NP 证明的直觉
• 为什么我们使用 SAT 求解器来处理大多数 NP 问题
• 零知识证明及其影响
• 量子计算及其含义
• 数学与计算机科学的关系

• 文字稿 http://t.cn/AXX4oal9

时间戳：

0000 - 开场
0108 - P vs NP
1451 - 如果放松正确性要求会怎样
2538 - 为什么 NP 完全问题等价
3033 - 空间 vs 时间复杂度
4306 - 为什么人们使用 SAT 求解器
4553 - 随机性是一种资源
5548 - 随机性取决于计算能力
012120 - 零知识证明及其重要性
013830 - 量子计算及其重要原因
015624 - 数学 vs 计算机科学
020816 - 重大突破及其经历
021231 - 对年轻时的自己的建议
021448 - 结尾

1. 失败与研究者生涯 - Avi 说，在他生命中的大多数日子里，他去上班，却无法完成自己想做的事情。他深入思考一个问题，却无法解决它。然而，每一次失败都教会他一些东西。即使是小小的收获，也让他感到满足。

因为在科技领域，我总是不断从我的检查清单上划掉项目。取得可衡量的进展一直让我感到满足。如果我一直无法从清单上划掉项目，我想象那可能会让人沮丧。

此外，突破是如此稀少。想象一下，花几十年时间研究一个问题，然后终于意识到解决方案。所以他说，作为一名研究者，享受思考这些问题的过程尤为重要。

2. “随机性在于观察者的计算能力眼中” - 这是他举的例子。假设我为你抛一枚硬币，你必须猜它是正面还是反面。你会给它落在正面或反面的几率是多少？显而易见的答案是 50%。

但是，如果有一台超级计算机连接到几个指向我手的摄像头呢。如果我抛那枚相同的硬币，你就能以近 100% 的确定性告诉我它会怎么落下来。事件本身并没有改变。改变的是你拥有的计算能力有多大。

3. 一些不可判定问题（例如停机问题）可以高效验证——在我见过的所有复杂性类别的维恩图中，我都假设不可判定问题是不可触及的。这确实如此，没有算法能判定所有实例。

然而，2020年的一项突破，利用多证明者量子交互证明，可以让我们用多项式时间验证器来验证像停机问题一样困难的问题。

这个证明（如果你好奇的话，论文名叫“MIP* = RE”），我当年特意写了一篇blog 题为《量子物理+复杂性科学+可计算性理论=？》，非常可怕。 http://t.cn/AXX4K35A