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
853

There is No Polynomial Deterministic Space Simulation of Two-Way Probabilistic Space with a Two-Way Random-Tape Generator
Marek Karpinski and Rutger Verbeek
[Download PostScript] [Download PDF]

We prove there is no polynomial deterministic space simulation for two-way random-tape 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 squared-space simulation (for recognizers and transducers) generalizes to the two-way random-tape machine model. We prove, in fact, a stronger result saying that even space-bounded Las~Vegas two-way random-tape 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