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.
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ 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))$. $\endgroup$– RaphaelMay 29, 2011 at 18:47
-
$\begingroup$ relevant question: cstheory.stackexchange.com/q/4448/1037 $\endgroup$– Artem Kaznatcheev ♦May 29, 2011 at 18:54
-
$\begingroup$ I am speaking about probabilistic not quantum turing machines. Can you further enlighten me with this question? $\endgroup$– jacob marleyMay 29, 2011 at 19:14
-
3$\begingroup$ It sounds like you're asking if RL contains NL ? $\endgroup$– Suresh VenkatMay 29, 2011 at 19:36
-
$\begingroup$ I think you are right, as I am not so familiar i didn't understand it in the first place $\endgroup$– jacob marleyMay 29, 2011 at 20:00
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
answered May 29, 2011 at 20:53
-
4$\begingroup$ 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,” yes, it is NL. $\endgroup$ May 29, 2011 at 21:55
-
$\begingroup$ 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. $\endgroup$– Cem SayMar 23, 2012 at 20:41