28.11.2008

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).