
University of Bonn > Department of Computer Science > Chair V  
CSReports 19851989  Copyright 19851989 University of Bonn, Department of Computer Science, Abt. V  
852 25.11.2008 
On the Power of TwoWay Random Generators and the Impossibility of Deterministic PolySpace 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 oneway readonly random tape. [BCP 83] asks: "Is it possible to extend our simulation results to the case of a twoway readonly oracle head? "In the same vein [FLS 83] suggests that it could be a difference between twoway and oneway random tape: "... for spacebounded 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 twoway random space classes that answers both questions. We prove that there is no polynomial deterministic space simulation of twoway random space. In fact our result is stronger, saying that the probabilistic twoway random tape algorithms are precisely exponential more powerful than the probabilistic onway random tape algorithms. 

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