# Simulating nondeterministic space-bounded computation using randomness

Let's suppose that a language $L \in$ NSPACE($f(n)$) where $f(n)$ is $O(\log n)$. And now let's suppose that I have a probabilistic Turing machine. Can this machine run in $O(f(n))$ space and answer yes when $x \in L$ with $\Pr(yes) > 1/2$ and answer no when $x \not\in L$ with $\Pr(no) = 1$? Let's suppose I dont care about time as long as the machine halts.

• 1) Please use LaTeX. 2) I assume you want $f(n) \in \omega(f(n))$ because the answer is trivial for $f \in \Theta(f(n))$. – Raphael May 29 '11 at 18:47
• relevant question: cstheory.stackexchange.com/q/4448/1037 – Artem Kaznatcheev May 29 '11 at 18:54
• I am speaking about probabilistic not quantum turing machines. Can you further enlighten me with this question? – jacob marley May 29 '11 at 19:14
• It sounds like you're asking if RL contains NL ? – Suresh Venkat May 29 '11 at 19:36
• I think you are right, as I am not so familiar i didn't understand it in the first place – jacob marley May 29 '11 at 20:00