Abstract
The prototypical result of relativized complexity theory is the theorem 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. However, some simple simulations, such as the alternation theorems of Chandra, Kozen and Stockmeyer (ALOGSPACE=P, AP=PSPACE, etc.), can fail in the presence of an oracle.
This paper examines the reasons for nonrelativizability and discusses how they can be overcome. A model for alternation oracle machines is presented in which ALOGSPACE=P and AP=PSPACE relativize to all oracles.
Research supported in part by an Alfred P. Sloan Foundation Doctoral Dissertation Fellowship.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
T. Baker, J. Gill, R. Solovay, “Relativizations of the P=? NP question,” SIAM J. Comput. 4 (1975) 431–452.
J. F. Buss, “Relativized Alternation and Space-Bounded Computation,” Ph.D. thesis, Massachusetts Institute of Technology, to appear, 1986.
A. K. Chandra, D. Kozen, L. J. Stockmeyer, “Alternation,” J. Assoc. Comput. Mach. 28 (1981) 114–133.
R. Ladner, N. Lynch, “Relativization of Questions about Log-Space Reducibility,” Math. Syst. Theory 10 (1976) 19–32.
N. Lynch, “Log Space Machines with Multiple Oracle Tapes,” Theor. Comput. Sci. 6 (1978) 25–39.
P. Orponen, “Complexity Classes of Alternating Machines with Oracles,” Automata, Languages and Programming, Lect. N. Comput. Sci. 154 (1983) 573–584.
P. Orponen, “General Nonrelativizability Results for Parallel Models of Computation,” Proc. of the Winter School on Theor. Comput. Sci., Lammi, Finland (1984) 194–205.
W. L. Ruzzo, J. Simon, M. Tompa, “Space-Bounded Hierarchies and Probabilistic Computation,” Proc. Fourteenth Ann. ACM Symp. Theory Comput. (1982) 215–223.
W. J. Savitch, “Relationships between Nondeterministic and Deterministic Tape Complexities,” J. Comput. Syst. Sci. 4 (1970) 177–192.
I. Simon, “On Some Subrecursive Reducibilities,” Ph.D. dissertation, Stanford University, Report STAN-CS-77-608 (1977).
C. B. Wilson, “Relativized Circuit Size and Depth,” Ph.D. thesis, University of Toronto, Technical Report 179/85 (1985). See also C. B. Wilson, “Parallel Computation and the NC hierarchy relativized,” these proceedings.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1986 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Buss, J.F. (1986). Relativized alternation. In: Selman, A.L. (eds) Structure in Complexity Theory. Lecture Notes in Computer Science, vol 223. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-16486-3_90
Download citation
DOI: https://doi.org/10.1007/3-540-16486-3_90
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-16486-9
Online ISBN: 978-3-540-39825-7
eBook Packages: Springer Book Archive