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.
Asked
Active
Viewed 241 times
2
Suresh Venkat
- 32,071
- 4
- 95
- 271
jacob marley
- 21
- 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))$.
– Raphael May 29 '11 at 18:47 -
relevant question: http://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
-
3It 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
1 Answers
5
My comment was incorrect, and in fact the answer to your question is YES. From Wikipedia:
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.
Suresh Venkat
- 32,071
- 4
- 95
- 271
-
4Note 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,” yes, it is NL. – Tsuyoshi Ito May 29 '11 at 21:55
-
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 Mar 23 '12 at 20:41