# Any known connections between open problems for time and space: P vs L, NP vs NL, BPP vs BPL, ⊕P vs ⊕L

It would be nice to show that $P=L$ implies $NP=NL$. Or, $NP=NL$ implies $UP=UL$. Or maybe, $⊕P = ⊕L$ implies $PP = PL$.

Are there any known connections between the problems: P vs L, UP vs UL, NP vs NL, ZPL vs ZPP, RL vs RP, BPP vs BPL, PP vs PL, or ⊕P vs ⊕L?

I just started to learn about probabilistic space complexity classes so for all I know there are known results or maybe this hasn't even been investigated thoroughly.

An incomplete list of results (correct me if any of them are wrong):

(1) $L \subseteq UL \subseteq NL$

(2) $L \subseteq ZPL \subseteq RL \subseteq BPL \subseteq PL$

(3) $RL \subseteq NL \subseteq PL \cap ⊕L$

(4) $PL \cup ⊕L \subseteq NC^2 \subseteq P$

One connection: if any of these problems have a positive answer, then we get $NC^2 = P$, $PSPACE = EXPTIME$, and $AL \neq AP$ where it is well known that $AL = P$ and $AP = PSPACE$.

For example, suppose that we have $PP=PL$. Then, we get $PL = NC^2 = P = PP$. And, $NC^2 = P$ implies $PSPACE = EXPTIME$. Further, we can't have $AL = AP$. Otherwise, we would get $P = PSPACE = EXPTIME$ which violates the time hierarchy theorem.

Any corrections, ideas, thoughts, results, or references are appreciated. Thank you for reading! :)

• Where are you getting NL = ZPL from? That seems unlikely to be known (or true). – Huck Bennett Apr 8 '15 at 22:24
• There are two extant definitions of randomized log space classes, depending on whether you also demand the running time to be polynomial or not. The uninteresting definition implies $\mathrm{ZPL}=\mathrm{RL}=\mathrm{NL}$, the interesting one does not. It seems that the notation in the list mixes up these two conventions. – Emil Jeřábek Apr 8 '15 at 22:44
• @HuckBennett Wikipedia says, "It is known that NL is equal to ZPL, the class of problems solvable by randomized algorithms in logarithmic space and unbounded time, with no error." – Michael Wehar Apr 9 '15 at 0:18
• @MichaelWehar Is $NC=PSPACE$ or $RNC=PSPACE$ possible? – T.... Jul 20 '18 at 15:24
• @Problem I could be mistaken, but I think $NC = PSPACE$ would imply $P = EXPTIME$ which violates the time hierarchy theorem. In other words, I think that $NC \neq PSPACE$. I'm not sure about $RNC$ though. I think these are neat questions!! :) – Michael Wehar Jul 20 '18 at 17:49