1965 Canada / United States P

Paths, Trees, and Flowers

Jack Edmonds, 1965 — polynomial time is the right definition of "tractable." The benchmark by which everything in this book is later judged hard.

Jack Edmonds, working at the National Bureau of Standards, gave the first polynomial-time algorithm for maximum matching in general graphs. In doing so he made the methodological argument that polynomial running time should be the formal definition of "efficient" — distinguishing algorithms whose cost grows as a power of the input size from algorithms whose cost grows exponentially. The argument, now called the Cobham–Edmonds thesis, is the reason "P" is the class it is. Without this paper there is no P, and without P there is no NP, and without NP there is no NP-hard. The complexity hierarchy this book uses to classify every later problem rests on the line Edmonds drew between polynomial and exponential cost.

In plain terms

Before Edmonds, "fast enough" was a vibe. An algorithm was good if it ran in reasonable time on the inputs you cared about. A few researchers had noticed that algorithms tend to fall into two families — those whose cost scales gently as the input grows, and those that explode — but no one had drawn the line formally and made the case. Edmonds drew the line and made the case. Polynomial running time, he argued, is the mathematically natural definition of efficiency. An algorithm in O(n²) or O(n³) is efficient; an algorithm in O(2ⁿ) is not, and on inputs of any size that matters it never will be. The argument is not that polynomial algorithms are always fast in practice — n¹⁰⁰ is polynomial and useless. The argument is that the gap between polynomial and exponential is the only gap that does not eventually close as hardware improves. An exponential algorithm cannot be saved by a faster computer. A polynomial algorithm can. This is the line that defines the class P. And once P exists, NP exists — the class of problems whose solutions can be verified in polynomial time. And once NP exists, NP-hard exists — the class at least as hard as NP. And once NP-hard exists, this entire book has a vocabulary. When chapter six tells you that test suite minimization is NP-complete and chapter eight tells you package dependency resolution is NP-complete, those statements only mean something because Edmonds drew this line first. He drew the line, and the matching algorithm in the same paper proved a problem could sit on the easy side of it. Maximum matching, against everyone's expectations at the time, turned out to be in P. The first easy side. The first hard side. The line every later page in this book stands on.