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.

$\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, 2023 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, 2023 at 3:03

0

Your Answer

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