# Are there any non-relativized separations between $L$ and $PH$?

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?

• 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? – Alex Meiburg Aug 28 '15 at 22:09
• 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 …) $\;\;\;\;\;\;\;\;$ – user6973 Aug 29 '15 at 13:29
• (… 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 …) $\;\;\;$ – user6973 Aug 29 '15 at 13:31
• (... 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. ​ ​ ​ ​ – user6973 Aug 22 '16 at 12:50
• 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. :) – Alex Meiburg Aug 22 '16 at 12:57