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

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


1 Answer 1


$\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.

  • $\begingroup$ How about $\oplus L$ vs $PSPACE$? $\endgroup$
    – Turbo
    Commented Feb 26, 2021 at 1:22
  • 1
    $\begingroup$ $\oplus \mathbf{L} \subseteq \mathbf{DSPACE}(\log^2 n)$ as well. One way to prove it is a variation of Savitch's algorithm. $\endgroup$ Commented Feb 26, 2021 at 6:33
  • $\begingroup$ Posted variant cstheory.stackexchange.com/questions/48491/…. $\endgroup$
    – Turbo
    Commented Feb 26, 2021 at 6:40

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.