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}$?

$\endgroup$

migrated from cstheory.stackexchange.com Aug 3 '12 at 21:42

This question came from our site for theoretical computer scientists and researchers in related fields.

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} $.)

$\endgroup$
  • 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 Aug 2 '12 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 Aug 2 '12 at 9:07
  • $\begingroup$ Don't you mean $ \mathsf{L} = \mathsf{RL} \cap \mathsf{coRL} $? $\endgroup$ – Uri Aug 2 '12 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 Aug 2 '12 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 Aug 2 '12 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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