Tim Roughgarden 以一个看似简单的问题开始：有没有计算机无法做到的事情？为了回答这个问题，他带我们回到1936年，当时阿兰·图灵在实际计算机出现十年前，就作为解决一个模糊数学问题的副产品奠定了计算机科学的基础。图灵的论文介绍了以他命名的理论机器，并证明了一个令人震惊的事实：有些问题是任何算法无法解决的，无论我们投入多少时间或计算能力。停机问题，即询问一个程序是否最终会停止运行，永远超出任何计算机的能力范围。在这个基础上，Roughgarden 转向了一个更微妙的问题。在计算机能够解决的问题中，哪些问题可以快速解决？他向我们介绍了算法捷径，这些聪明的技巧让程序避免检查每一个可能的解决方案。你手机的地图应用程序基于 Dijkstra 算法找到最短路径，而无需检查每一个可想象的路径。Karatsuba 的乘法方法超越了我们都学过的学校方法。这些捷径似乎几乎是魔法，它们激发了一种自然的希望：或许每个问题都有这样的捷径。然而，这种希望与旅行推销员问题 (TSP) 碰撞在一起。尽管看起来与最短路径路由几乎相同，TSP 抵抗了每一个寻找快速算法的尝试。Roughgarden 解释了这个难题是如何导致 NP-完全性理论的形成，这是计算机科学中最令人惊讶的发现之一。成千上万看似无关的问题（调度、解谜、网络优化）竟然被发现是同一潜在挑战的伪装版本。如果有人为其中的任意一个问题找到了快速算法，那么所有问题都变得简单。如果任何一个问题确实很难，那么所有问题都是困难的。这将我们带到了 P 与 NP，计算机科学中最重要的未解之问，也是数学中的一个伟大未解问题。Roughgarden 追溯了这个问题的历史，通过希尔伯特、哥德尔和冯·诺依曼等人物，展示了两个独立的研究传统，一个专注于算法能实现的成果，另一个关注它们的局限性，如何汇聚到这个单一的问题上。课程最后讨论了这个问题的答案可能对密码学、人工智能、量子计算及我们对计算本身的理解意味着什么。无需计算机科学或数学的背景知识。你可以观看下面的讲座，浏览章节索引，或在 YouTube 上观看。Tim Roughgarden 是高等研究所数学学院的教授。他之前在哥伦比亚大学的计算机科学系工作了七年，又在斯坦福大学待了15年。他的主要研究兴趣在于计算机科学与经济学之间的联系，以及算法的设计、分析和局限性。他是《算法博弈论的二十个讲座》、《超越算法的最坏情况分析》和《算法照亮》系列的作者，以及许多研究文章的撰写者。他的工作获得了几个理论计算机科学的重大奖项，包括 ACM Grace Murray Hopper 奖和哥德尔奖。