Easy Problems, Hard Problems

Building on his earlier discussion of shortest paths and Dijkstra's algorithm, Tim Roughgarden asks a crucial question: do efficient algorithmic shortcuts always exist? Starting with the Traveling Salesman Problem, he shows that some problems can be solved in principle but appear to resist any efficient solution. This leads to a careful explanation of polynomial-time algorithms, the class P, and why the distinction between polynomial and exponential growth matters so profoundly, especially in the age of Moore's Law. Roughgarden then introduces NP problems, those for which solutions are easy to verify, and explains how the concept of reductions allows mathematicians to prove that certain problems are "NP-complete," at least as hard as every other problem in NP. He recounts the stories of Stephen Cook and Leonid Levin, whose independent discoveries of NP-completeness required remarkable tenacity, setting the stage for a deeper exploration of P versus NP.