25.11.2008

[BCP 83] proves that both probabilistic acceptors and transducers working in space S(n) ≥ log n can be simulated by deterministic machines in O(f(n)²) space. The definition of probabilistic computations uses one-way read-only random tape. [BCP 83] asks: "Is it possible to extend our simulation results to the case of a two-way read-only oracle head? "In the same vein [FLS 83] suggests that it could be a difference between two-way and one-way random tape: "... for space-bounded probabilistic computations where the space bound is much less than the length of y, it could matter." (y denoting the random tape inscription). In this paper we give a full characterization of two-way random space classes that answers both questions. We prove that there is no polynomial deterministic space simulation of two-way random space. In fact our result is stronger, saying that the probabilistic two-way random tape algorithms are precisely exponential more powerful than the probabilistic on-way random tape algorithms.