Article

Free access

Space-bounded hierarchies and probabilistic computations

Authors:

Walter L. Ruzzo,

Janos Simon,

Martin TompaAuthors Info & Claims

STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing

Pages 215 - 223

https://doi.org/10.1145/800070.802194

Published: 05 May 1982 Publication History

PDF eReader

Abstract

This paper studies two aspects of the power of space-bounded probabilistic Turing machines. Section 2 presents a simple alternative proof of Simon's recent result [13] that space-bounded probabilistic complexity classes are closed under complement. Section 3 demonstrates that any language in the log n space hierarchy can be recognized by an log n space-bounded probabilistic Turing machine with small error; this is a generalization of Gill's result that any language in NSPACE(log n) can be recognized by such a machine

The second result raises interesting questions about space hierarchies, which are considered in section 4. The usual definition is in terms of space-bounded alternating Turing machines with a constant number of alternations [4].

References

[1]

Aleliunas, R., Karp, R.M., Lipton, R.J., Lov-&-aacute;sz, L., and 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.

Digital Library

Google Scholar

[2]

Angluin, D., On Relativizing Auxiliary Pushdown Machines, Mathematical Systems Theory 13, 4 (1980), 283-299.

Google Scholar

[3]

Borodin, A., Cook, S. and Pippenger, N., Space-Bounded Probabilistic Computations, in preparation.

Google Scholar

[4]

Chandra, A.K., Kozen, D.C., and Stockmeyer, L.J., Alternation, Journal of the ACM 28, 1 (January 1981), 114-133.

Digital Library

Google Scholar

[5]

Gill, J., Computational Complexity of Probabilistic Turing Machines, SIAM Journal on Computing 6, 4 (December 1977), 675-695.

Digital Library

Google Scholar

[6]

Ladner, R.E. and Lynch, N.A., Relativization of Questions About Log Space Computability, Mathematical Systems Theory 10, 1 (1976), 19-32.

Crossref

Google Scholar

[7]

Lewis, H.R. and Papadimitriou, C.H., Symmetric Space-Bounded Computation, Technical Report TR-08-80, Harvard University, Aiken Computation Laboratory, August, 1980.

Google Scholar

[8]

Lynch, N., Log Space Recognition and Translation of Parenthesis Languages, Journal of the ACM 24, 4 (October 1977), 583-590.

Digital Library

Google Scholar

[9]

Peterson, W.W., "Error-Correcting Codes", The M.I.T. Press and John Wiley -&-amp; Sons, New York, 1961.

Google Scholar

[10]

Reif, J.H., Symmetric Alternation, Technical Report TR-07-81, Harvard University, Aiken Computation Laboratory, July, 1981.

Google Scholar

[11]

Ruzzo, W.L., On Uniform Circuit Complexity, Journal of Computer and System Sciences 22, 3 (June 1981), 365-383.

Crossref

Google Scholar

[12]

Simon, I., On Some Subrecursive Reducibilities, Ph.D. Thesis, Stanford University, April 1977. Computer Science Department Technical Report STAN-CS-77-608.

Digital Library

Google Scholar

[13]

Simon, J., Space-Bounded Probabilistic Turing Machine Complexity Classes are Closed under Complement, Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing, Milwaukee, Wisconsin (May 1981), 158-167.

Digital Library

Google Scholar

[14]

Stockmeyer, L.J., The Polynomial-Time Hierarchy, Theoretical Computer Science 3 (1976), 1-22.

Crossref

Google Scholar

Cited By

View all

Herman GSoltys M(2019)Unambiguous Functions in Logarithmic SpaceFundamenta Informaticae10.5555/2384787.2384789114:2(129-147)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.5555/2384787.2384789
Macarie I(2007)Multihead two-way probabilistic finite automataTheory of Computing Systems10.1007/BF0267945530:1(91-109)Online publication date: 30-Jul-2007
https://doi.org/10.1007/BF02679455
Macarie I(2005)Multihead two-way probabilistic finite automataLATIN '95: Theoretical Informatics10.1007/3-540-59175-3_103(371-385)Online publication date: 6-Jun-2005
https://doi.org/10.1007/3-540-59175-3_103
Show More Cited By

Space-bounded hierarchies and probabilistic computations
1. Theory of computation
  1. Computational complexity and cryptography
  2. Models of computation
    1. Computability

Recommendations

Reversal-bounded computations
Alternation for sublogarithmic space-bounded alternating pushdown automata

This paper investigates infinite hierarchies on alternation-depth and alternation-size of alternating pushdown automata (apda's) with sublogarithmic space. We first show that there is an infinite hierarchy on alternation-depth for apda's with ...
Closure properties of the classes of sets recognized by space-bounded two-dimensional probabilistic turing machines

This paper investigates closure properties of the classes of sets recognized by spacebounded two-dimensional probabilistic Turing machines with error probability less than 12. Let 2-PTM(L(m,n)) be the class of sets recognized by L(m,n) space-bounded two-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing

May 1982

408 pages

ISBN:0897910702

DOI:10.1145/800070

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 May 1982

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
122
Total Downloads

Downloads (Last 12 months)58
Downloads (Last 6 weeks)5

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Herman GSoltys M(2019)Unambiguous Functions in Logarithmic SpaceFundamenta Informaticae10.5555/2384787.2384789114:2(129-147)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.5555/2384787.2384789
Macarie I(2007)Multihead two-way probabilistic finite automataTheory of Computing Systems10.1007/BF0267945530:1(91-109)Online publication date: 30-Jul-2007
https://doi.org/10.1007/BF02679455
Macarie I(2005)Multihead two-way probabilistic finite automataLATIN '95: Theoretical Informatics10.1007/3-540-59175-3_103(371-385)Online publication date: 6-Jun-2005
https://doi.org/10.1007/3-540-59175-3_103
Macarie I(2005)Space-efficient deterministic simulation of probabilistic automataSTACS 9410.1007/3-540-57785-8_135(109-122)Online publication date: 31-May-2005
https://doi.org/10.1007/3-540-57785-8_135
Buss J(2005)Relativized alternationStructure in Complexity Theory10.1007/3-540-16486-3_90(66-76)Online publication date: 2-Jun-2005
https://doi.org/10.1007/3-540-16486-3_90
Jung H(2005)On probabilistic tape complexity and fast circuits for matrix inversion problemsAutomata, Languages and Programming10.1007/3-540-13345-3_25(281-291)Online publication date: 28-May-2005
https://doi.org/10.1007/3-540-13345-3_25
Volger H(2005)Rudimentary relations and Turing machines with linear alternationLogic and Machines: Decision Problems and Complexity10.1007/3-540-13331-3_38(131-136)Online publication date: 30-May-2005
https://doi.org/10.1007/3-540-13331-3_38
Beigel RBin Fu (1997)Circuits over PP and PLProceedings of Computational Complexity. Twelfth Annual IEEE Conference10.1109/CCC.1997.612297(24-35)Online publication date: 1997
https://doi.org/10.1109/CCC.1997.612297
Jung H(1985)On probabilistic time and spaceAutomata, Languages and Programming10.1007/BFb0015756(310-317)Online publication date: 1985
https://doi.org/10.1007/BFb0015756
Maffioli ESperanza MVercellis C(1984)Randomized algorithms: An annotated bibliographyAnnals of Operations Research10.1007/BF018743961:3(331-345)Online publication date: Oct-1984
https://doi.org/10.1007/BF01874396
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

Reversal-bounded computations

Alternation for sublogarithmic space-bounded alternating pushdown automata

Closure properties of the classes of sets recognized by space-bounded two-dimensional probabilistic turing machines