<p>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$.</p>

<p>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?</p>

<p>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.</p>

<p>An incomplete list of results (correct me if any of them are wrong):</p>

<p>(1) $L \subseteq UL \subseteq NL$</p>

<p>(2) $L \subseteq ZPL \subseteq RL \subseteq BPL \subseteq PL$</p>

<p>(3) $RL \subseteq NL \subseteq PL \cap ⊕L$</p>

<p>(4) $PL \cup ⊕L \subseteq NC^2 \subseteq P$</p>

<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$.</p>

<p>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.</p>

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

CC BY-SA 3.0
2015-04-08T22:24:35.313Z
Where are you getting NL = ZPL from? That seems unlikely to be known (or true).
Huck Bennett
CC BY-SA 3.0
2015-04-08T22:44:28.717Z
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
CC BY-SA 3.0
2015-04-09T00:18:25.753Z
@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
CC BY-SA 3.0
2015-04-09T00:19:33.890Z
Link: http://en.wikipedia.org/wiki/NL_%28complexity%29#Containments
Michael Wehar
CC BY-SA 3.0
2015-04-09T00:28:16.890Z
I see now.  Thanks!  I will fix it so that ZPL above means logspace and polynomial time.  :)
Michael Wehar
CC BY-SA 4.0
2018-07-20T15:24:46.660Z
@MichaelWehar Is $NC=PSPACE$ or $RNC=PSPACE$ possible?
Turbo
CC BY-SA 4.0
2018-07-20T17:49:31.610Z
@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
<space-complexity><logspace><structural-complexity><complexity><probabilistic-complexity>
Any known connections between open problems for time and space: P vs L, NP vs NL, BPP vs BPL, ⊕P vs ⊕L
Michael Wehar
# Any known connections between open problems for time and space: P vs L, NP vs NL, BPP vs BPL, ⊕P vs ⊕L

(Asked by: username_0 on 2015-04-08)

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! :)

**Tags:** space-complexity, logspace, structural-complexity, complexity, probabilistic-complexity

> **Comments:**
> **username_1**: Where are you getting NL = ZPL from? That seems unlikely to be known (or true).  
> **username_2**: 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.  
> **username_0**: @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."  
> **username_0**: Link: http://en.wikipedia.org/wiki/NL_%28complexity%29#Containments  
> **username_0**: I see now.  Thanks!  I will fix it so that ZPL above means logspace and polynomial time.  :)  
> **username_3**: @MichaelWehar Is $NC=PSPACE$ or $RNC=PSPACE$ possible?  
> **username_0**: @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!!  :)  

---

## 0 answers

