
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 19851989  Copyright 19851989 Universität Bonn, Institut für Informatik, Abt. V  
8510 01.12.2008 
Randomness, Provability, and the Separation of Monte Carlo Time and Space
Marek Karpinski and Rutger Verbeek [Download PostScript] [Download PDF]
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 (n^{log n}) ∪_{ε} Monte Carlo Time (2^{nε}). 

Last Change:
12/01/08 at 13:39:45
English 
Universität Bonn > Institut für Informatik > Abteilung V 