
University of Bonn > Department of Computer Science > Chair V  
CSReports 19851989  Copyright 19851989 University of Bonn, Department of Computer Science, Abt. V  
853

There is No Polynomial Deterministic Space Simulation of TwoWay Probabilistic Space with a TwoWay RandomTape Generator
Marek Karpinski and Rutger Verbeek [Download PostScript] [Download PDF] We prove there is no polynomial deterministic space simulation for twoway randomtape probabilistic space (Pr$_2$SPACE) (as defined in \cite{BCP83}) for all functions $f : \: \NN \rightarrow \NN$ and all $\alpha \in \NN, \, \prtwospace(f(n)) \not\subseteq \dspace(f(n)^{\alpha})$. This is answer to the problem formulated in op cit., whether the deterministic squaredspace simulation (for recognizers and transducers) generalizes to the twoway randomtape machine model. We prove, in fact, a stronger result saying that even spacebounded Las~Vegas twoway randomtape algorithms (yielding always the correct answer and terminating with probability 1) are exponentially more efficient than the deterministic ones. 

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