Cook's theorem
Cook showed that Boolean satisfiability is the hardest problem in its class: every problem whose solution can be checked quickly reduces to it.
Why it matters
A line appeared between what can be checked and what can be found, the question that still governs what is reasonable to ask of a machine.
The paper introduces what was later named NP-completeness and poses P versus NP. For AI this is not an abstraction: state-space search, constraint satisfaction and first-order inference are all problems of the same nature. Heuristics are needed not because the algorithms are imperfect but because exhaustive search is infeasible in principle.