5
$\begingroup$

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

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Where are you getting NL = ZPL from? That seems unlikely to be known (or true). $\endgroup$
    – Huck Bennett
    Apr 8, 2015 at 22:24
  • 5
    $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Apr 8, 2015 at 22:44
  • $\begingroup$ @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." $\endgroup$
    – Michael Wehar
    Apr 9, 2015 at 0:18
  • 1
    $\begingroup$ @MichaelWehar Is $NC=PSPACE$ or $RNC=PSPACE$ possible? $\endgroup$
    – Turbo
    Jul 20, 2018 at 15:24
  • 1
    $\begingroup$ @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!! :) $\endgroup$
    – Michael Wehar
    Jul 20, 2018 at 17:49

0

Reset to default

Your Answer

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