MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 2 down vote accepted

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.

share|cite|improve this answer

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.