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

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

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

CC BY-SA 3.0
2015-08-28T22:09:44.613Z
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
CC BY-SA 3.0
2016-08-22T12:57:14.480Z
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
<polynomial-hierarchy><logspace><separation>
Are there any non-relativized separations between $L$ and $PH$?
Alex Meiburg
# Are there any non-relativized separations between $L$ and $PH$?

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

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?

**Tags:** polynomial-hierarchy, logspace, separation

> **Comments:**
> **username_0**: 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?  
> **username_0**: 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. :)  

---

## 0 answers

