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

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

-
There may be an interesting question here, but I really don't understand your notation. You know that you can use TeX? –  Dylan Thurston May 28 '11 at 15:12
Are you asking if a non-deterministic machine with space f(n) can solve the same problems as a one-sided error randomized machine with space f(n)? –  Robin Kothari May 29 '11 at 3:55
I edited the question to reflect my understanding of the meaning; I hope I got it right. –  Dylan Thurston May 29 '11 at 20:54

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.

-

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

-
I'm not aware of any result of the sort you want, with only linear increase in the space used. Note though, that "I'm not aware of ..." is more a statement of how little I know than about the actual status of the problem. (If you allowed quadratic increase, you wouldn't need randomization, by Savitch's theorem.) –  Andreas Blass May 29 '11 at 23:00