I.OWER BOUNDS ON GRAPH THREADING !JY PROBABIIJSTIC MACHINES (preliminary verslon)
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 . ( 10g2n : space log n) requlres space 0 I 1 J by random og ogn machines, even if 'fast· is relaxed to mean only 'subex- ponential'. In particular. the lower bound on space holds for the time complexity of Savitch's algorithm (Which can be simulated in the model).l Introduction. We study space-bounded probabilistic computations, where both the error probability and the computation time are required to be reasonable. We recapitulate some facts about probabilistic space-bounded Turing machines (the reader familiar with (G), (RST), (8) may wish to skip this paragraph). Space bounds are imposed deterulinistically at the beginning of the computation. From then on, the transi tion function also depends on the outcome of an unbiased coin, and the computation becomes a stochas tic process. Acceptance of string % by machine may be defined in several ways: unrestricted: the probability Pll(x). of the event M reaches an accepting configuration on input x is greater than 1/2.