Lower bounds on graph threading by probabilistic machines
Piotr Berman, Janoš Šimon · 1983
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).