On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes (Q1094874)

A probabilistic Turing machine M that computes the function \(f_ M\) is called Monte Carlo Turing machine if for all inputs x the probability of M to compute \(f_ M(x)\) is greater than 3/4. A function \(f: {\mathbb{N}}\to {\mathbb{N}}\) is called Monte Carlo constructible if there is a Monte Carlo Turing machine with space bound f(n) such that for all n there is a string x, \(| x| =n\), with \(f_ M(x)=f(n)\). The authors prove that for every unbounded nondecreasing recursive function f there is an unbounded nondecreasing Monte Carlo constructible minorant g with g(n)\(\leq f(n)\) for all n. Then, it is shown that if g is Monte Carlo constructible and \(f=o(g)\), then the probabilistic space complexity class PrSPACE(g) strictly includes the Monte Carlo space complexity class MSPACE(f). Finally the authors show the existence of a set that is in the terminating Monte Carlo space complexity class \(M^ TSPACE(\log \log n)\) and that is not in the class NSPACE(o(log n)).