There is no polynomial deterministic space simulation of probabilistic space with a two-way random-tape generator
From MaRDI portal
Publication:3716302
DOI10.1016/S0019-9958(85)80032-2zbMath0588.68026MaRDI QIDQ3716302
Rutger Verbeek, Marek Karpinski
Publication date: 1985
Published in: Information and Control (Search for Journal in Brave)
Related Items
On some variations of two-way probabilistic finite automata models, A survey of space complexity, On read-once vs. multiple access to randomness in logspace, On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape