1
$\begingroup$

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?

Answering D.W.

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Jan 28 at 17:27
  • $\begingroup$ @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 $\endgroup$
    – l4m2
    Jan 29 at 3:03

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.