4
$\begingroup$

In one sense, $P$ vs. $PSPACE$ is the "easiest" first step to showing $P \neq NP$... and this is one you hear often about. In a different sense, you could take $L$ at one end and then $PH$ at the other. Is anything known about this question, whether $L \stackrel{?}{=} PH$?

There is this separation guaranteed by $L \neq PSPACE$, and so the weakest unanswered questions are when you circumvent the time- and space-hierarchy theorems by either asking to strengthen the lower side into a time-bound class (giving $P \stackrel{?}{=} PSPACE$), or by weakening the harder side into a time-bound class (giving $L \stackrel{?}{=} PH$).

It seems that I only ever hear about the first question though, and not the latter. Besides the question of the actual relation between the two classes, is there a reason why one question is so much more popular than the other?

Improve this question
$\endgroup$
5
  • $\begingroup$ Interesting, thank you. I wasn't able to find anything on $AC^0(6)$ =?= L, though -- only that $AC^0 \subseteq NC^1 \subseteq L$ (but that is without the mod-6 gate). Do you happen to know anything? Also, would you happen to have a source where they state that $AC^0(6)$ =?= Almost-PSPACE is open? $\endgroup$
    – Alex Meiburg
    Aug 28, 2015 at 22:09
  • $\begingroup$ For non-uniform circuits or any reasonable uniformity condition, $\: AC^{\hspace{.02 in}0} \hspace{-0.05 in}\subseteq AC^{\hspace{.02 in}0}\hspace{-0.03 in}[6] \subseteq$ TC$^{\hspace{.02 in}0}$ $\hspace{-0.04 in}\subseteq NC^1 \;$. $\:\:$ (I wrote (6) instead of [6] in my previous comment because I couldn't figure out how to put the latter into a link.) $\;\;\;$ (continued …) $\;\;\;\;\;\;\;\;$ $\endgroup$
    – user6973
    Aug 29, 2015 at 13:29
  • $\begingroup$ (… continued) $\;\;\;\;\;\;\;\;$ Additionally, $\;\;\;$ L-uniform $NC^1 \subseteq \: L \;\;\;\;$. $\;\;\;\;\;\;\;\;$ However, it's far from clear that P-uniform $NC^1 \subseteq \: L \;\;\;\;$. $\;\;\;\;\;\;\;\;$ I don't know of any source for the problem I gave being open, $\:$ (continued …) $\;\;\;$ $\endgroup$
    – user6973
    Aug 29, 2015 at 13:31
  • $\begingroup$ (... continued) ​ and contrary to my now-deleted speculation from almost a year ago, #P was and is known to not have weakly-uniform TC$^0$ circuits, so by this paper, the same applies to PP. ​ ​ ​ ​ $\endgroup$
    – user6973
    Aug 22, 2016 at 12:50
  • $\begingroup$ Man! Correcting yourself so much later, and you couldn't have waited one extra week to make it an anniversary! :P -- but honestly, these are some cool papers it looks like! Thanks a bunch. :) $\endgroup$
    – Alex Meiburg
    Aug 22, 2016 at 12:57

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.