Space-bounded hierarchies and probabilistic computations
From MaRDI portal
Publication:1062759
DOI10.1016/0022-0000(84)90066-7zbMath0573.68021OpenAlexW2012539169MaRDI QIDQ1062759
Walter L. Ruzzo, Martin Tompa, Janos Simon
Publication date: 1984
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(84)90066-7
alternation hierarchyoracle hierarchylog n spaceRuo, Walter L.Simon, Janosspace-bounded probabilistic complexity classesTompa, Martin
Related Items
Alternating and empty alternating auxiliary stack automata., Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n)\(\neq NSPACE(\log \,n)\), Self-reducibility, Positive relativizations for log space computability, Decompositions of nondeterministic reductions, Relativized alternation and space-bounded computation, On the complexity of deciding fair termination of probabilistic concurrent finite-state programs, A measure of relativized space which is faithful with respect to depth, The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\), Empty alternation, RelativizedNC, Logics capturing relativized complexity classes uniformly, Minimal Reversible Deterministic Finite Automata, New developments in structural complexity theory, Space-efficient informational redundancy, Isolation, matching, and counting uniform and nonuniform upper bounds, Space-bounded quantum complexity, Relationships among $PL$, $\#L$, and the determinant, An NL hierarchy, Decreasing the bandwidth of a transition matrix, Multihead two-way probabilistic finite automata, A survey of space complexity, Upper bounds on recognition of a hierarchy of non-context-free languages, Diagonalization, uniformity, and fixed-point theorems, A very hard log-space counting class, On read-once vs. multiple access to randomness in logspace, A trichotomy for regular simple path queries on graphs, Reductions to graph isomorphism, Unnamed Item, Circuits over PP and PL, Nonuniform complexity classes specified by lower and upper bounds, A note on closure properties of logspace MOD classes, Consistency in nondeterministic storage, Amplification of slight probabilistic advantage at absolutely no cost in space, Relativizing small complexity classes and their theories
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Deterministic simulation of tape-bounded probabilistic Turing machine transducers
- On uniform circuit complexity
- Symmetric space-bounded computation
- The polynomial-time hierarchy
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- On relativizing auxiliary pushdown machines
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Alternation
- Relativization of questions about log space computability
- Computational Complexity of Probabilistic Turing Machines
- Log Space Recognition and Translation of Parenthesis Languages
