# 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). Apr 8, 2015 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. Apr 8, 2015 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." Apr 9, 2015 at 0:18
• @MichaelWehar Is $NC=PSPACE$ or $RNC=PSPACE$ possible? Jul 20, 2018 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!! :) Jul 20, 2018 at 17:49