Favorite Theorems: The First Decade

I have listed my favorite theorems for the first and second decades of my research career corresponding roughly to the third and fourth decades of research in computational complexity. This year I will list my favorite theorems for the first decade of complexity, 1965-1974.

As opposed to the previous lists, we have 30-40 years of hindsight to see what theorems have stood the test of time. Each month starting in February I will highlight one result and mention related work to show how computational complexity went from a simple but beautiful idea to an important subdiscipline of computer science.