01 · A life in computing
The person behind the work
Richard Karp helped explain why many important optimization problems resist efficient exact solutions. His work showed that a broad collection of combinatorial problems are NP-complete by connecting them through polynomial-time reductions. At Berkeley, he also developed algorithms and investigated approaches to difficult problems. His research gave computer scientists a shared framework for distinguishing tractable tasks from problems whose apparent difficulty requires different strategies.
The contribution, explained
Richard Karp connected a broad collection of combinatorial problems through polynomial-time reductions. If an efficient exact algorithm existed for one NP-complete problem, these translations could transfer that power to the others. His work also developed efficient algorithms for network flow and other optimisation tasks.
Why it matters
Understanding problem structure guides the choice between exact methods, approximation, heuristics and specialised algorithms.