精读预计 2 分钟

Computation as a universal and fundamental concept

摘要

文章开篇以 1936 年图灵停机问题引入：计算机是否能解决所有问题？再分析快速解法的算法技巧，如 Dijkstra 算法与 Karatsuba 乘法法，接着聚焦旅行商问题与 NP 完全性，发现数百个看似 unrelated 的问题其实共享同一挑战。作者追踪 P vs NP 历史，并探讨答案对密码学、人工智能、量子计算及计算本身理解的意义。

荐读理由

AI 追求 1 秒内解 TSP 的路线图，算力或量子计算都无解，P vs NP 问题彻底改变了算法效率的判断标准

原文

Computation as a Universal and Fundamental Concept

Tim Roughgarden begins with a deceptively simple question: is there anything computers cannot do? To answer it, he takes us back to 1936, when Alan Turing, a decade before actual computers existed, laid the foundations of computer science as a byproduct of solving an obscure mathematical problem. Turing's paper introduced the theoretical machine that bears his name and proved something startling: there are problems no algorithm can ever solve, no matter how much time or computing power we throw at them. The halting problem, which asks whether a program will eventually stop running, is forever beyond the reach of any computer.

From this foundation, Roughgarden pivots to a more subtle question. Among the problems computers can solve, which ones can they solve quickly? He introduces us to algorithmic shortcuts, clever tricks that let programs avoid examining every possible solution. Your phone's map application builds on Dijkstra's algorithm to find the shortest route without checking every conceivable path. Karatsuba's multiplication method beats the grade-school approach we all learned. These shortcuts seem almost magical, and they raise a natural hope: perhaps such shortcuts exist for every problem.

That hope crashes against the Traveling Salesman Problem. Despite looking nearly identical to shortest-path routing, TSP has resisted every attempt to find a fast algorithm. Roughgarden explains how this puzzle led to the theory of NP-completeness, one of computer science's most surprising discoveries. Thousands of seemingly unrelated problems (scheduling, puzzle-solving, network optimization) turn out to be disguised versions of the same underlying challenge. If anyone finds a fast algorithm for any one of them, all become easy. If any one is truly hard, all are hard.

This brings us to P versus NP, the most important open question in computer science and one of the great unsolved problems in mathematics. Roughgarden traces its history through figures like Hilbert, Gödel, and von Neumann, showing how two separate research traditions, one focused on what algorithms can achieve, the other on their limitations, converged on this single question. The course concludes by examining what the answer might mean for cryptography, artificial intelligence, quantum computing, and our understanding of computation itself. No prior background in computer science or mathematics is required.

You can watch the lectures below, browse the chapter index, or watch on YouTube.

Tim Roughgarden

Tim Roughgarden is a Professor in the School of Mathematics at the Institute for Advanced Study. He previously spent seven years on the computer science faculty at Columbia and 15 years at Stanford. His main interests are in the connections between computer science and economics, and in the design, analysis, and limits of algorithms.

He is the author of Twenty Lectures on Algorithmic Game Theory, Beyond the Worst-Case Analysis of Algorithms, and the Algorithms Illuminated series, as well as numerous research articles. His work has been recognized with several major awards in theoretical computer science, including the ACM Grace Murray Hopper Award and the Gödel Prize.

Continue where you left off