On read-once vs. multiple access to randomness in logspace
From MaRDI portal
Publication:1208412
DOI10.1016/0304-3975(93)90258-UzbMath0774.68037WikidataQ29027264 ScholiaQ29027264MaRDI QIDQ1208412
Publication date: 16 May 1993
Published in: Theoretical Computer Science (Search for Journal in Brave)
multiple access; randomness; randomized logspace machine; randomized space-bounded computation; read- once access; two-sided error; zero error
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems, Pseudorandom generators for combinatorial checkerboards, Pseudorandom generators, typically-correct derandomization, and circuit lower bounds, Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs, \(\text{RL}\subseteq \text{SC}\), How strong is Nisan's pseudo-random generator?, Running time analysis of broadcast consensus protocols, On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape
Cites Work
- Space-bounded hierarchies and probabilistic computations
- There is no polynomial deterministic space simulation of probabilistic space with a two-way random-tape generator
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- Nondeterministic Space is Closed under Complementation
- Two Applications of Inductive Counting for Complementation Problems
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Computational Complexity of Probabilistic Turing Machines
