Randomness, provability, and the separation of Monte Carlo Time and space

Separation theorems are essential in complexity theory: looking for strict lower and upper bounds makes sense only in the context of a hierarchy theorem. For probabilistic complexity classes with deterministically constructible bounds the standard diagonalization techniques can be applied and yield at least as dense hierarchies as in the deterministic case. For Monte Carlo (i.e. bounded error probability) classes the situation is quite different. On one hand we can construct arbitrarily slowly growing Monte Carlo space constructible functions (even far below log log n) [KV 86], on the other hand the existence of different — even deterministically constructible — bounds is not sufficient for a proof of separation. Up to now there is no way to separate, e.g., Monte Carlo Time (n) from Monte Carlo Time (nlog n). We are able, however, to display a method of separating Monte Carlo Time (nlogn) from $$\mathop \cap \limits_\varepsilon$$ Monte Carlo Time (2nε).Note that the Monte Carlo property of probabilistic algorithms is II₁-complete. For diagonalization, however, an enumerable set of machines is required. For practical purposes the only interesting Monte Carlo algorithms are those which are provable in some reasonable theory (e.g. within Peano arithmetic or Zermelo-Fraenkel set theory). For such provable complexity classes dense space and time hierarchies are established, space hierarchies even below log log n or log*n.