Timeline for What is known about coRL and RL?
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 28, 2023 at 15:24 | comment | added | l4m2 | @Kaveh So we know RL=ZPL but we don't know ZPL=?L right? | |
| Aug 3, 2012 at 21:42 | history | migrated | from cstheory.stackexchange.com (revisions) | ||
| Aug 3, 2012 at 11:01 | vote | accept | Uri | ||
| Aug 2, 2012 at 22:33 | comment | added | Kaveh | @Uri, no, it isn't the definition of L. The definition uses deterministic Turing machines (DTM), not probabilistic Turing machines (PTM). The languages in the intersection have two separate log-space PTMs each giving answers with zero error on one side. For comparison, we don't know if ZPP=P. | |
| Aug 2, 2012 at 20:46 | comment | added | Sasho Nikolov | 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. | |
| Aug 2, 2012 at 16:48 | comment | added | Uri | But languages which are in the conjunction can be determined without error on both sides, and we're using logarithmic space. Isn't that exactly the definition of $\mathsf{L}$? | |
| Aug 2, 2012 at 15:52 | comment | added | Sasho Nikolov | 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? | |
| Aug 2, 2012 at 11:56 | comment | added | Uri | Don't you mean $ \mathsf{L} = \mathsf{RL} \cap \mathsf{coRL} $? | |
| Aug 2, 2012 at 9:07 | comment | added | Abuzer Yakaryilmaz | @SashoNikolov: Thank you! I have updated my answer. The proof for "coRL intersect RL is L" in my mind was certainly wrong. | |
| Aug 2, 2012 at 7:54 | comment | added | Sasho Nikolov | 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 | |
| Aug 2, 2012 at 6:40 | history | answered | Abuzer Yakaryilmaz | CC BY-SA 3.0 |