Some Observations about Relativization of Space Bounded Computations
Juris Hartmanis, Richard Chang, Jim Kadin, Stephen G. Mitchell · WORLD SCIENTIFIC eBooks · 1993
In this column we explore what relativization says about space bounded computations and what recent results about space bounded computations say about relativization. There is a strong belief in computational complexity circles that problems which can be relativized in two contradictory ways are very hard to solve. We believe that such problems can only be solved by proof techniques that do not relativize. For example, standard diagonalization methods are powerless in these cases [BGS75, HH76, Hop84]. So far only very simple problems with contradictory relativizations have been solved [Har85, Cha90]. Unfortunately, many important problems in complexity theory have contradictory relativizations and have to be viewed as inaccessible to our current proof techniques. The classic example is the P? = NP problem for which Baker, Gill and Solovay [BGS75] exhibited recursive oracles A and B such that P A = NP A and P B � = NP B. Since then, a large number of other computational complexity problems have been shown to have contradictory relativizations and so far none of them have been solved. 1 Today, a proof that a problem has contradictory relativizations is viewed as strong evidence that the problem cannot be solved by current proof techniques and such