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)
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (4)
On some variations of two-way probabilistic finite automata models ⋮ On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape ⋮ A survey of space complexity ⋮ On read-once vs. multiple access to randomness in logspace
This page was built for publication: There is no polynomial deterministic space simulation of probabilistic space with a two-way random-tape generator