Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The complexity class RL is described at the complexity zoo as: Has the same relation to L as RP does to P. The randomized machine must halt with probability 1 on any input. It must also run in polynomial time (since otherwise we would just get NL).

The question is - how can we get NL when omitting the demand for polynomial time? I have a solution of my own but it seems strange to me.

My solution: If suffices to solve ST-CON. We can use the same NL algorithm for ST-CON (guessing a path) with one major difference - we count the number of steps we make, and if it suppresses the number of vertices in the graph, we restart the computation, without remembering ANYTHING.

This means we can play this game indefinitely. If the graph is not ST-connected, then we'll never halt, but if it's ST-connected we'll halt in probability 1 (this is the same as saying that a geometric random variable obtains a finite value in probability 1). However, since we do not halt for NO-instances, this solution "feels wrong" to me.

Is there another solution? And is my solution correct?

share|improve this question
    
@Gadi: having the only tag be computer-science makes it look like this question is not appropriate for a math-based Q&A site. Could you please remedy this by adding a "mathier" tag? –  Pete L. Clark Sep 16 '10 at 13:02
1  
Added some tags. However, it is my belief that theoretical computer science IS mathematics... –  Gadi A Sep 16 '10 at 13:15
    
@Gadi A: regardless of your beliefs, the fact remains that there are probably more people qualified to answer this question at cstheory.stackexchange.com than here. –  Qiaochu Yuan Sep 16 '10 at 17:21
1  
@Qiaochu: My guess is that this will be closed there. That site is akin to MathOverflow for CS. This looks like a homework problem to me. btw, Gadi, did you check the wiki for NL? –  Aryabhata Sep 16 '10 at 17:54
    
@Gadi, btw, your proof looks right to me, though I am not sure (rusty regarding the definitions). I believe there is no condition that a NDTM should halt on every computation path. –  Aryabhata Sep 16 '10 at 18:01

1 Answer 1

up vote 3 down vote accepted

Your solution is almost correct.

In the definition of RL, we require that the algorithm halt with probability $1$ on any input. As you note, your algorithm runs forever on "No" instances. To fix this, we'll take advantage of the fact that we're allowed a small chance of error. In particular, we're allowed to sometimes reject "Yes" instances, as long as we never accept a "No" instance.

The basic idea is to keep a counter of how many iterations we've used so far. If a path exists, we should find it within $2N^N$ iterations (with probability at least $3/4$). So if we've gone that long without finding a valid path, we'll reject the graph. Note that we'll never accept a bad graph this way, and we'll rarely reject a good graph.

We can't naively count to $N^N$, however, since this would require $N\lg N$ space. Instead, we'll probabilistically "count" that high.

After each iteration, we'll flip $N\lg N + 2$ coins. If every coin lands heads, then we stop (and reject the graph). If at least one coin lands tails, then we begin another iteration. This can be done in log-space, since we only need to count how many flips have occurred.

The probability of getting all heads is $1/2^{N\lg N + 2}=1/4N^N$, so with probability at least $3/4$, this won't happen until at least $2N^N$ iterations have elapsed.

Taking a union bound over both ways the algorithm could fail, we see that everything works with probability at least $1/2$.

Finally, note that this halts with probability $1$, since we'll flip all heads eventually.

share|improve this answer

Your Answer

 
discard

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.