Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1985-1989 Copyright 1985-1989 University of Bonn, Department of Computer Science, Abt. V
852

25.11.2008

On the Power of Two-Way Random Generators and the Impossibility of Deterministic Poly-Space Simulation
Marek Karpinski and Rutger Verbeek
[Download PostScript] [Download PDF]

[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)2) 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.

Last Change: 11/25/08 at 14:30:52
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V