Tim Roughgarden：计算是宇宙的终极法则

Computation as a Universal and Fundamental Concept

Tim Roughgarden 从 Alan Turing 在 1936 年提出的理论出发，带我们重新审视计算的边界。他揭示了著名的停机问题，证明了有些难题无论算力多强都无法解决。课程深入探讨了算法捷径的魔力，从 Dijkstra 算法到 Karatsuba 乘法，展示了如何高效解决问题。然而，Traveling Salesman Problem 的出现打破了“所有问题都有捷径”的幻想，引出了计算机科学中最核心的 P versus NP 难题。Tim Roughgarden 梳理了从 Hilbert 到 von Neumann 的思想脉络，指出这一未解之谜将如何重塑我们对密码学、人工智能和量子计算的理解。无需任何数学背景，即可跟随这位顶级学者的思路，探索计算作为宇宙基本概念的深刻内涵。

"如果有人在任何一个 NP 完全问题上找到了快速算法，那么所有这类问题都将迎刃而解；反之，如果其中任何一个问题确实很难，那么它们全部都难如登天。"