Institut für Informatik   Abteilung V

 Universität Bonn -> Institut für Informatik -> Abteilung V CS-Reports 1993 Copyright 1993 Universität Bonn, Institut für Informatik, Abt. V 85104 Lower Space Bounds for Randomized Computation Rusins Freivalds, Marek Karpinski [Download PostScript] [Download PDF] It is a fundamental open problem in the randomized computation how to separate different randomized time or randomized small space classes (cf., e.g., [KV 87], [KV 88]). In this paper we study lower space bounds for randomized computation, and prove lower space bounds up to log $n$ for the specific sets computed by the Monte Carlo Turing machines. This enables us for the first time, to separate randomized space classes below log $n$ (cf. [KV 87], [KV 88]), allowing us to separate, say, the randomized space ${\mathcal O} (1)$ from the randomized space ${\mathcal O} (\log^*n)$. We prove also lower space bounds up to log log $n$ and log $n$, respectively, for specific languages computed by probabilistic Turing machines, and one--way probabilistic Turing machines. Last Change: 11/05/14 at 09:49:14  English Universität Bonn -> Institut für Informatik -> Abteilung V