Karp's twenty-one problems
Karp showed that 21 practical problems, from graph colouring to scheduling and packing, are exactly as hard as satisfiability.
Why it matters
Cook's result stopped being isolated and became a map: it showed how many useful problems lie beyond fast solution.
The list includes the travelling salesman, vertex cover, clique and knapsack. For AI it meant the boundary did not run alongside the field's problems but straight through them. After this, heuristic search, approximation and restricted domains stopped being a compromise and became the only answer.