<p><span class="math-container">$\mathbf{UL}$</span> is contained in <span class="math-container">$\mathbf{NL}$</span>, which is contained in <span class="math-container">$\mathbf{DSPACE}(\log^2 n)$</span> by Savitch's theorem, which is strictly contained in <span class="math-container">$\mathbf{PSPACE}$</span> by the space hierarchy theorem, so <span class="math-container">$\mathbf{UL}$</span> is strictly contained in <span class="math-container">$\mathbf{PSPACE}$</span>. It would be surprising if e.g. <span class="math-container">$\mathbf{UL} = \mathbf{DSPACE}(\log^2 n)$</span>, but I don't think it's known to be false.</p>

CC BY-SA 4.0
2021-02-26T01:22:09.487Z
How about $\oplus L$ vs $PSPACE$?
Turbo
CC BY-SA 4.0
2021-02-26T06:33:43.363Z
$\oplus \mathbf{L} \subseteq \mathbf{DSPACE}(\log^2 n)$ as well. One way to prove it is a variation of Savitch's algorithm.
William Hoza
CC BY-SA 4.0
2021-02-26T06:40:45.237Z
Posted variant https://cstheory.stackexchange.com/questions/48491/bigger-collapse-and-savitchs-theorem.
Turbo
CC BY-SA 4.0
2021-02-25T06:39:23.983Z
2021-02-25T06:39:23.983Z
William Hoza
<p><span class="math-container">$L\neq DSPACE[\omega(\log n)]$</span> is known.</p>
<p>Is <span class="math-container">$UL\neq DSPACE[\omega(\log n)]$</span> and <span class="math-container">$UL\neq PSPACE$</span> known?</p>

<space-complexity><hierarchy-theorems>
Is $UL\neq PSPACE$ known?
Turbo
# Is $UL\neq PSPACE$ known?

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

$L\neq DSPACE[\omega(\log n)]$ is known.

Is $UL\neq DSPACE[\omega(\log n)]$ and $UL\neq PSPACE$ known?

**Tags:** space-complexity, hierarchy-theorems


---

## 1 answers

### Answer by username_1 on 2021-02-25. Score: 11 | Accepted answer

$\mathbf{UL}$ is contained in $\mathbf{NL}$, which is contained in $\mathbf{DSPACE}(\log^2 n)$ by Savitch's theorem, which is strictly contained in $\mathbf{PSPACE}$ by the space hierarchy theorem, so $\mathbf{UL}$ is strictly contained in $\mathbf{PSPACE}$. It would be surprising if e.g. $\mathbf{UL} = \mathbf{DSPACE}(\log^2 n)$, but I don't think it's known to be false.

> **Comments:**
> **username_0**: How about $\oplus L$ vs $PSPACE$?  
> **username_1**: $\oplus \mathbf{L} \subseteq \mathbf{DSPACE}(\log^2 n)$ as well. One way to prove it is a variation of Savitch's algorithm.  
> **username_0**: Posted variant https://cstheory.stackexchange.com/questions/48491/bigger-collapse-and-savitchs-theorem.  

---

