<p>This is equivalent to <span class="math-container">$LOGSPACE≠NP$</span> (which is obviously open). The proof of that equivalence relativizes (at least under the usual oracle models).</p>
<p>And there are oracles making <span class="math-container">$LOGSPACE = NP$</span> (the PSPACE-complete TQBF works) and making them not equal (the oracle separating P from NP works).</p>

CC BY-SA 4.0
2021-02-19T14:16:28.833Z
2021-02-19T14:16:28.833Z
Ryan Williams
<p>Is it known whether <span class="math-container">$Logspace$</span> is <strong>strictly</strong> contained in the polynomial time hierarchy ?</p>
<p>Are there oracles relative to which these classes are equal / distinct ?</p>

CC BY-SA 4.0
2021-02-18T11:30:16.537Z
No, this is not known. For all we know, PH may collapse to uniform $\mathrm{AC}^0[6]$.
Emil Jeřábek
<oracles><polynomial-hierarchy><logspace>
It is known that $L \subsetneq PH$?
GBathie
# It is known that $L \subsetneq PH$?

(Asked by: username_0 on 2021-02-18)

Is it known whether $Logspace$ is **strictly** contained in the polynomial time hierarchy ?

Are there oracles relative to which these classes are equal / distinct ?

**Tags:** oracles, polynomial-hierarchy, logspace
> **Comments:**
> **username_1**: No, this is not known. For all we know, PH may collapse to uniform $\mathrm{AC}^0[6]$.  

---

## 1 answers

### Answer by username_2 on 2021-02-19. Score: 8 | Accepted answer

This is equivalent to $LOGSPACE≠NP$ (which is obviously open). The proof of that equivalence relativizes (at least under the usual oracle models).

And there are oracles making $LOGSPACE = NP$ (the PSPACE-complete TQBF works) and making them not equal (the oracle separating P from NP works).


---

