Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
Abteilung V

Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1985-1989 Copyright 1985-1989 Universität Bonn, Institut für Informatik, Abt. V


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
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope