# How can $R_HL$ differ from $RL$?

https://complexityzoo.net/Complexity_Zoo:R

RL: Randomized Logarithmic-Space 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).

Contains RHL.

While requiring runtime in polynomial time avoids trivial RL=NL, it also allows running time stored. If an algorithm would on average take $$f(n)$$ steps, then trying to run $$100f(n)$$ steps would only have 1% chance of not halting, and rejecting in this case doesn't harm.

So why only "Contains RHL" shown?

What does "allows running time stored" mean?

Logarithmic-Space allows storing polynomial-size integer

What do you mean by "rejecting doesn't harm"?

If X is in RL, then there's an algorithm that accept for 51% chance for input in X, and we can construct one that accept for 50% chance and never fall into infinite loop

Why do you think the two classes should be equal? Their definitions are different.

RHL: Randomized Halting Logarithmic-Space

Has the same relation to L as RP does to P. The randomized machine must halt for every input and every setting of the random tape.

• What does "allows running time stored" mean? What do you mean by "rejecting doesn't harm"? Why do you think the two classes should be equal? Their definitions are different.
– D.W.
Jan 28, 2023 at 17:27
• @D.W. Logarithmic-Space allows storing polynomial-size integer. If X is in RL, then there's an algorithm that accept for 51% chance for input in X, and we can construct one that accept for 50% chance and never fall into infinite loop
– l4m2
Jan 29, 2023 at 3:03