Relativized alternation and space-bounded computation (Q1111024): Difference between revisions

Baker, Gill and Solovay showed in 1975 that there exist double relativizations of the \(P=? NP\) question. This is generally taken as evidence that the underlying unrelativized problem is difficult to solve. In this paper it is argued that the failure of unrelativized simulation in the relativized case is due to unequal oracle access mechanisms. The alternation model is therefore considered. Relative to this model nearly all known Turing machine simulations hold with respect to any oracle set.