Lower bounds on graph threading by probabilistic machines

It is likely that reliable and fast space-bounded probabilistic acceptors are less powerful than nondeterministic ones. We consider a restricted model of space-bounded probabilistic computation, the random analog of a model studied in [CR]. We show that maze traversal (a complete problem for nondeterministic space log n) requires space Ω(log2n/loglogn) by random machines, even if ´fast´ is relaxed to mean only ´subexponential´. In particular, the lower bound on space holds for the time complexity of Savitch´s algorithm (which can be simulated in the model).