Computational Complexity

Tuesday, March 21, 2006

 
Favorite Theorems: Relativization

Posted by Lance

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.

7:58 PM #

1.  Jonathan Katz says:  
   
   There is also, of course, this paper, which points out (among other things) that non-relativizing results were known well before interactive proofs came along.
   

   9:39 PM, March 21, 2006