Relativization: a Revisionistic Retrospective
Juris Hartmanis, Richard Chang, Suresh T. Chari, Desh Ranjan, Pankaj Rohatgi · WORLD SCIENTIFIC eBooks · 1993
In this column we examine the role of relativization in complexity theory in light of recent non-relativizing results involving interactive protocols. We begin with the twice-told tale of the relativization principle and ponder upon its possible demise. Then, we discuss whether usual assumptions are historically accurate. 1 The Twice-Told Tale For almost two decades, contradictory relativization has been a central theme in complexity theory. This concept was first introduced by Baker, Gill and Solovay [BGS75] in their ground breaking paper where they exhibited oracles A and B such that P A = NP A and P B � = NP B. This result was startling because almost all results in recursion theory remain true in the presence of oracles and most techniques used in complexity theory had been resource bounded versions of those used in recursion theory. Baker, Gill and Solovay offered the following explanation of their results [BGS75]: We feel that this is further evidence of the difficulty of the P? = NP question....It seems unlikely that ordinary diagonalization methods are adequate for producing an example of a language in NP but not in P; such diagonalizations, we would expect, would apply equally well to the relativized classes....On the other hand, we do not feel that one can give a general method for simulating nondeterministic machines by deterministic machines in polynomial time, since such a method should apply as well to relativized machines.