Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-APX-Reports 1993 Copyright 1993 University of Bonn, Department of Computer Science, Abt. V
8916

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
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V