Space-bounded hierarchies and probabilistic computations
type: Item
instance of: scholarly article
title: Space-bounded hierarchies and probabilistic computations
zbMATH Open document ID: 0573.68021
DOI: 10.1016/0022-0000(84)90066-7
author: Walter L. Ruzzo
author: Janos Simon
author: Martin Tompa
published in: Journal of Computer and System Sciences
publication date: 1984-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 3915628
zbMATH Keywords: Ruo, Walter L.
zbMATH Keywords: Simon, Janos
zbMATH Keywords: Tompa, Martin
zbMATH Keywords: space-bounded probabilistic complexity classes
zbMATH Keywords: oracle hierarchy
zbMATH Keywords: alternation hierarchy
zbMATH Keywords: log n space
MaRDI profile type: Publication
full work available at URL: 0022-0000(84)90066-7
OpenAlex ID: W2012539169
cites work: On relativizing auxiliary pushdown machines
cites work: Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
cites work: Parallel computation for well-endowed rings and space-bounded probabilistic machines
cites work: Alternation
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: Deterministic simulation of tape-bounded probabilistic Turing machine transducers
cites work: Relativization of questions about log space computability
cites work: Symmetric space-bounded computation
cites work: Log Space Recognition and Translation of Parenthesis Languages
cites work: Q3290963
cites work: On uniform circuit complexity
cites work: Q4194464
cites work: Q4139697
cites work: The polynomial-time hierarchy
Recommended article: On the Structure of Logspace Probabilistic Complexity Classes
Recommended article: Q4247197
Recommended article: On the structure of log-space probabilistic complexity classes
Recommended article: Probabilistic complexity classes and lowness
Recommended article: Lower space bounds for randomized computation
Recommended article: Probabilistic Recursion Theory and Implicit Computational Complexity
Recommended article: On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape
Recommended article: Hardness and hierarchy theorems for probabilistic quasi-polynomial time
Recommended article: Time-space trade-off lower bounds for randomized computation of decision problems
description: scientific article; zbMATH DE number 3915628