We trace computational complexity theory from Kurt Gödel's 1956 letter to von Neumann, through the foundational work of Hartmanis and Stearns, Cook's and Levin's discovery of NP-completeness, the barrier theorems that explain why proving P ≠ NP is so hard, and Ryan Williams' surprising connection between faster algorithms and lower bounds.