4
$\begingroup$

Wondering about any known relations between $\mathsf{RL}$ complexity class (one sided error with logarithmic space) and its complementary class, $\mathsf{coRL}$.

Are they the same class?

What are $\mathsf{coRL}$'s relation to $\mathsf{NL}$, $\mathsf{P}$?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
8
$\begingroup$

By definition, $ \mathsf{RL} $ is a subset of $ \mathsf{NL} $, and so $ \mathsf{coRL} $ is a subset of $ \mathsf{coNL} $.

Since $ \mathsf{NL} = \mathsf{coNL} $, $ \mathsf{coRL} $ is also subset of $ \mathsf{NL} $.

Moreover, $ \mathsf{NL} \subseteq \mathsf{P} $.

Please also note that although it is widely believed to be true, whether $ \mathsf{RL} \subseteq \mathsf{L} $ is still an open problem, and so is whether $ \mathsf{coRL} \subseteq \mathsf{L} $. (The obviuos relation is $ \mathsf{L} \subseteq \mathsf{RL} \cap \mathsf{coRL} $.)

Improve this answer
$\endgroup$
8
  • 4
    $\begingroup$ for the fact, you can try to figure it out on your own or check Arora-Barak. the paper linked does way more. but I do not understand why coRL intersect RL is L, can you explain? it seems to me to be the class of languages recognizable by expected polynomial time zero error logspace machines. note that long before reingold's algorithm a zero error logspace algorithm was known for st-connectivity ( see here) and this did not "obviously" imply that st-connectivity is in logspace $\endgroup$
    – Sasho Nikolov
    Commented Aug 2, 2012 at 7:54
  • $\begingroup$ @SashoNikolov: Thank you! I have updated my answer. The proof for "coRL intersect RL is L" in my mind was certainly wrong. $\endgroup$
    – Abuzer Yakaryilmaz
    Commented Aug 2, 2012 at 9:07
  • $\begingroup$ Don't you mean $ \mathsf{L} = \mathsf{RL} \cap \mathsf{coRL} $? $\endgroup$
    – Uri
    Commented Aug 2, 2012 at 11:56
  • 1
    $\begingroup$ Uri, $\mathsf{L} = \mathsf{RL} \cap \mathsf{coRL}$ does not appear to be known, unless you assume $\mathsf{L} = \mathsf{RL}$ (see my comment). BTW, aren't both RL and coRL are in NL by guessing the randomness? $\endgroup$
    – Sasho Nikolov
    Commented Aug 2, 2012 at 15:52
  • 2
    $\begingroup$ Think about this: suppose you run the RL algorithm and the coRL one in parallel and the RL algorithm rejects and the coRL algorithm accepts. One of them made a mistake. Which one? The only obvious solution is to repeatedly run the algorithms until either the RL algorithm accepts or the coRL algorithm rejects, and that's zero error expected polynomial time, but with probability 0 may even not halt. $\endgroup$
    – Sasho Nikolov
    Commented Aug 2, 2012 at 20:46

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.