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?