<p>My comment was incorrect, and in fact the answer to your question is YES. From <a href="http://en.wikipedia.org/wiki/NL_%28complexity%29">Wikipedia</a>: </p>

<blockquote>
  <p>Suppose C is the complexity class of
  problems solvable in logarithmithic
  space with probabilistic Turing
  machines that never accept incorrectly
  but are allowed to reject incorrectly
  less than 1/3 of the time; this is
  called one-sided error. The constant
  1/3 is arbitrary; any x with 0 ≤ x &lt;
  1/2 would suffice.</p>
  
  <p>It turns out that C = NL. Notice that
  C, unlike its deterministic
  counterpart L, is not limited to
  polynomial time, because although it
  has a polynomial number of
  configurations it can use randomness
  to escape an infinite loop. If we do
  limit it to polynomial time, we get
  the class RL, which is contained in
  but not known or believed to equal NL.</p>
</blockquote>

CC BY-SA 3.0
2011-05-29T21:55:29.657Z
Note that the question specifies that the machine “halts.”  If we interpret this as “halts always,” then I think the class is RL, not NL.  If we interpret it as “halts [with probability 1](http://en.wikipedia.org/wiki/Almost_surely),” yes, it is NL.
Tsuyoshi Ito
CC BY-SA 3.0
2012-03-23T20:41:52.410Z
What is the difference between “halts always” and “halts with probability 1?” After being confused about this for a long time, mainly because Oded Goldreich redefines RSPACE to incorporate a time bound in his lecture notes, I have been finally convinced by the survey of Saks and a paper by Watrous that RSPACE(s)=NSPACE(s) for any space bound s; so in particular, for s= log n. RL, originally a shorthand for RSPACE(log n), nowadays denotes the more interesting class of languages that are recognized with positive one-sided error by logspace PTMs with polynomial time bounds.
Cem Say
CC BY-SA 3.0
2011-05-29T20:53:27.840Z
2011-05-29T20:53:27.840Z
Suresh Venkat
<p>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) &gt; 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.</p>

CC BY-SA 3.0
2011-05-29T18:47:11.160Z
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
CC BY-SA 3.0
2011-05-29T18:54:30.207Z
relevant question: http://cstheory.stackexchange.com/q/4448/1037
Artem Kaznatcheev
CC BY-SA 3.0
2011-05-29T19:14:16.150Z
I am speaking about probabilistic not quantum turing machines. Can you further enlighten me with this question?
jacob marley
CC BY-SA 3.0
2011-05-29T19:36:23.043Z
It sounds like you're asking if RL contains NL ?
Suresh Venkat
CC BY-SA 3.0
2011-05-29T20:00:08.900Z
I think you are right, as I am not so familiar i didn't understand it in the first place
jacob marley
<cc.complexity-theory><randomness><space-bounded><nondeterminism>
Simulating nondeterministic space-bounded computation using randomness
jacob marley
# Simulating nondeterministic space-bounded computation using randomness

(Asked by: username_0 on 2011-05-29)

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.

**Tags:** cc.complexity-theory, randomness, space-bounded, nondeterminism

> **Comments:**
> **username_1**: 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))$.  
> **username_2**: relevant question: http://cstheory.stackexchange.com/q/4448/1037  
> **username_0**: I am speaking about probabilistic not quantum turing machines. Can you further enlighten me with this question?  
> **username_3**: It sounds like you're asking if RL contains NL ?  
> **username_0**: I think you are right, as I am not so familiar i didn't understand it in the first place  

---

## 1 answers

### Answer by username_3 on 2011-05-29. Score: 5

My comment was incorrect, and in fact the answer to your question is YES. From [Wikipedia](http://en.wikipedia.org/wiki/NL_%28complexity%29):

> Suppose C is the complexity class of
> problems solvable in logarithmithic
> space with probabilistic Turing
> machines that never accept incorrectly
> but are allowed to reject incorrectly
> less than 1/3 of the time; this is
> called one-sided error. The constant
> 1/3 is arbitrary; any x with 0 ≤ x <
> 1/2 would suffice.
>
> It turns out that C = NL. Notice that
> C, unlike its deterministic
> counterpart L, is not limited to
> polynomial time, because although it
> has a polynomial number of
> configurations it can use randomness
> to escape an infinite loop. If we do
> limit it to polynomial time, we get
> the class RL, which is contained in
> but not known or believed to equal NL.

> **Comments:**
> **username_4**: Note that the question specifies that the machine “halts.”  If we interpret this as “halts always,” then I think the class is RL, not NL.  If we interpret it as “halts [with probability 1](http://en.wikipedia.org/wiki/Almost_surely),” yes, it is NL.  
> **username_5**: What is the difference between “halts always” and “halts with probability 1?” After being confused about this for a long time, mainly because Oded Goldreich redefines RSPACE to incorporate a time bound in his lecture notes, I have been finally convinced by the survey of Saks and a paper by Watrous that RSPACE(s)=NSPACE(s) for any space bound s; so in particular, for s= log n. RL, originally a shorthand for RSPACE(log n), nowadays denotes the more interesting class of languages that are recognized with positive one-sided error by logspace PTMs with polynomial time bounds.  

---

