Can i achieve something better with the probabilistic turing machine in matter of space?

Question

Let's suppose that a language $L \in \operatorname{NSPACE}(f(n))$ where $f(n) = \Omega(\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 for a $x \in L$ with Pr(yes)>1/2 and for a x that doesn't belong,answer no with Pr(no)=1? Le's suppose i dont care about time

Answer 1

Yes, if you do not care about running time, then you can simulate nondeterminism by a randomized algorithm with only a linear increase in space.

Assume that $f(n)\ge\log n$ is space-constructible, and let $L\in\mathrm{NSPACE}(f)$. By definition, there exists a nondeterministic Turing machine $M_0$ working in space $f(n)$ which accepts $L$. By the Immerman–Szelepcsényi theorem, there exists a nondeterministic Turing machine $M_1$ working in space $O(f(n))$ which accepts the complement of $L$. Since $f$ is space-constructible, we can endow both TM with a clock counting to $2^{O(f(n))}$ (an upper bound on the number of configurations of $M_i$) to ensure that both machines terminate on every input and for any nondeterministic choices.

Let $M$ be the following randomized algorithm. First, simulate $M_0$ by taking randomized choices instead of nondeterminism. If it accepts, then $M$ accepts. Otherwise, simulate $M_1$; if it accepts, then $M$ rejects. Otherwise, repeat the whole procedure.

Clearly, $M$ works in space $O(f(n))$, and when it halts, it always gives the correct answer. Moreover, with probability $1$, $M$ has to eventually halt, since either $M_0$ or $M_1$ has a positive probability of accepting. Thus, $M$ is a zero-error probabilistic algorithm for $L$. (The expected running time of $M$ may be as bad as exponential in the number of configurations of $M_i$, hence doubly exponential in $f(n)$.)

Note that there are conflicting definitions of randomized space classes in the literature. Some authors use RL to denote one-sided randomized logarithmic space without further restrictions, which by the argument above coincides with NL. Others require in addition the algorithm to run in polynomial time, and then it gives a presumably weaker class situated between L and NL.

Answer 2

Exactly. And I also demand the problem to require NSPACE(s(n)) s(n) = Ω(logn) in the nondetermintistic machine and O(s(n)) in the probabilistic