Lower Space Bounds for Randomized Computation

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], [KF 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 O(1) from the randomized space O(log* n). We prove also lower space bounds up to log log n and log n, respectively, for specific sets computed by probabilistic Turing machines, and one-way probabilistic Turing machines.

ICSI Technical Report TR-94-049

Technical Report