Relativized alternation and space-bounded computation

摘要

The prototypical results of relativized complexity theory are the theorems of Baker, Gill, and Solovay that the answer to the relativized P=? NP question depends on the oracle. Such results are commonly taken as evidence of the difficulty of solving the unrelativized case, on the assumption that simple simulations and diagonalizations generalize to oracle machines. Many simple simulations, however, fail in the presence of an oracle. Most of these simulations, but not all, involve space-bounded machines, for which there is no agreement on the proper model. The failure of any unrelativized simulation in the relativized case is shown to be due to unequal oracle access. In order to determine the proper oracle access for space-bounded machines, alternating machines are considered. A model in which ALOGSPACE = P, AP = PSPACE, etc., hold relative to any oracle is given. The alternation model gives a new model for deterministic space-bounded oracle machines and also affects time-bounded oracle machines slightly. In the new model, nearly all known Turing machine simulations hold relative to any oracle.