Space-bounded hierarchies and probabilistic computations. (English) Zbl 0573.68021

Ruzzo, Walter L.; Simon, Janos; Tompa, Martin

J. Comput. Syst. Sci. 28, 216-230 (1984).

First the paper gives a simple proof of Simon’s result that space-bounded probabilistic complexity classes are closed under complement. Main results concern new definition of space-bounded ”oracle hierarchy”. The entire log n space ”alternation hierarchy” is contained in the 2nd level of the log n space ”oracle hierarchy”. However, the entire log n space ”oracle hierarchy” is contained in bounded-error probabilistic space log n. This entails interesting consequences.

Reviewer: A.Slisenko

MSC:

68Q25	Analysis of algorithms and problem complexity
68Q05	Models of computation (Turing machines, etc.) (MSC2010)

Keywords:

Ruo, Walter L.; Simon, Janos; Tompa, Martin; space-bounded probabilistic complexity classes; oracle hierarchy; alternation hierarchy; log n space

References:

[1]	Adleman, L., Two theorems on random polynomial time, (19th Annual Symposium on Foundations of Computer Science (October 1978)), 75-83
[2]	Aleliunas, R.; Karp, R. M.; Lipton, R. J.; Lovasz, L.; Rackoff, C., Random walks, universal traversal sequences, and the complexity of maze problems, (20th Annual Symposium on Foundations of Computer Science (October 1979)), 218-223
[3]	Angluin, D., On relativizing auxiliary pushdown machines, Math. Systems Theory, 13, 4, 283-299 (1980) · Zbl 0426.68023
[4]	Bennett, C. H.; Gill, J., Relative to a random oracle \(A, P^A\) ≠ \(NP^A\) ≠ co-\(NP^A\) with probability 1, SIAM J. Comput., 10, 1, 96-112 (1981) · Zbl 0454.68030
[5]	Borodin, A.; Cook, S.; Pippenger, N., Parallel computation for well-endowed rings and spacebounded probabilistic machines, (Technical Report # 162/83 (April 1983), University of Toronto) · Zbl 0598.68043
[6]	Chandra, A. K.; Kozen, D. C.; Stockmeyer, L. J., Alternation, J. Assoc. Comput. Mach., 28, 1, 114-133 (January 1981) · Zbl 0473.68043
[7]	Gill, J., Computational complexity of probabilistic Turing machines, SIAM J. Comput., 6, 4, 675-695 (December 1977) · Zbl 0366.02024
[8]	Gill, J.; Hunt, J.; Simon, J., Deterministic simulation of tape-bounded probabilistic Turing machine transducers, Theoret. Comput. Sci., 12, 3, 333-338 (1980) · Zbl 0442.68034
[9]	Karp, R. M.; Lipton, R. J., Some connections between nonuniform and uniform complexity classes, (Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing (April 1980)), 302-309
[10]	Ladner, R. E.; Lynch, N. A., Relativization of questions about log space computability, Math. Systems Theory, 10, 1, 19-32 (1976) · Zbl 0341.68036
[11]	Lewis, H. R.; Papadimitriou, C. H., Symmetric space-bounded computation, Theoret. Comput. Sci., 19, 161-187 (1982) · Zbl 0491.68045
[12]	Lynch, N., Log space recognition and translation of parenthesis languages, J. Assoc. Comput. Mach., 24, 4, 583-590 (October 1977) · Zbl 0401.68051
[13]	Peterson, W. W., Error-Correcting Codes (1961), MIT Press: MIT Press Cambridge, Mass, and Wiley, New York · Zbl 0105.32802
[14]	Reif, J. H., Symmetric complementation, (Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing. Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, San Francisco, California (May 1982)), 201-214
[15]	Ruzzo, W. L., On uniform circuit complexity, J. Comput. System Sci., 22, 3, 365-383 (June 1981) · Zbl 0462.68013
[16]	Savitch, W. J., A note on relativized log space, (Technical Report CS-055 (March 1982), University of California: University of California San Diego) · Zbl 0407.68055
[17]	Simon, I., On some subrecursive reducibilities, (Ph.D. thesis (April 1977), Stanford University)
[18]	Simon, J., On the difference between one and many, (Automata, Languages, and Programming. Automata, Languages, and Programming, Lecture Notes in Computer Science, Vol. 52 (1977), Springer-Verlag: Springer-Verlag New York/Berlin), 480-491 · Zbl 0364.68066
[19]	Simon, J., Space-bounded probabilistic Turing machine complexity classes are closed under complement, (Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing. Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing, Milwaukee, Wisconsin (May 1981)), 158-167
[20]	Sipser, M., A complexity theoretic approach to randomness, (Proceedings of the 15th Annual ACM Symposium on Theory of Computing. Proceedings of the 15th Annual ACM Symposium on Theory of Computing, Boston, Massachusetts (May 1983)), 330-335
[21]	Stockmeyer, L. J., The polynomial-time hierarchy, Theoret. Comput. Sci., 3, 1-22 (1977) · Zbl 0353.02024