Favorite Theorems: Relativization

February Edition
After the work of Cook and Karp popularized the P versus NP question, computer scientists immediately tried hard to prove P=NP or P≠NP. Baker, Gill and Solovay showed that most of their approaches were doomed to failure.

Theodore Baker, John Gill, Robert Solovay, Relativization of the P=?NP Question, SICOMP 1975.
Baker, Gill and Solovay noted that complexity proofs relativized, that is held even if all machines involved could make queries to some "oracle," i.e., making queries to some fixed set. They created oracles A and B such that

• P^A = NP^A
• P^B ≠ NP^B

If one had a relativizable proof that P ≠ NP then the proof would also show P^A ≠ NP^A, contradicting their theorem. Baker et. al. give a few more relativization results and we've seen hundreds more since.
The paper gives very little about the philosophical implications of their results. For a short while some researchers thought that these results could lead to true independence of the P versus NP question, but this thinking was quickly abandoned and later we have seen some theorems that do not relativize, particularly in the area of interactive proof systems.
Relativization results do help us understand what theorems to pursue, what techniques cannot solve our questions. Nearly all the techniques we know for time classes, outside of the algebraic techniques used for interactive proofs, do relativize. Only a very few of the known relativization results later had proofs in the opposite direction.
For more read my 1994 survey The Role of Relativization in Complexity Theory.