Institut für Informatik   Abteilung V

 Universität Bonn -> Institut für Informatik -> Abteilung V CS-Reports 1985-1989 Copyright 1985-1989 Universität Bonn, Institut für Informatik, 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  English Universität Bonn -> Institut für Informatik -> Abteilung V