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
854

28.11.2008

Ont the Monte Carlo Space Constructible Functions and Separation Results for Probabilistic Complexity Classes
(Revised Version)

Marek Karpinski and Rutger Verbeek
[Download PostScript] [Download PDF]

It is proven that contrary to the deterministic and nondeterministic cases there is no recursive lower bound for Monte Carlo space constructible functions. The existence of small constructible bounds enables the separation of Monte Carlo space f(n) from probabilistic space g(n) (f(n) = o(g(n))) and - together with a new halting lemma for probabilistic machines with small space bounds - a hierarchy of "provable" Monte Carlo space classes with small bounds. We are also able to separate O(log log n) terminating Monte Carlo space in the sense of [AKLLR 79], [We 83] from NSPACE(log log n).

Last Change: 11/28/08 at 14:11:22
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V