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

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


$\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$ – 1.. Feb 26 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$ – William Hoza Feb 26 at 6:33
  • $\begingroup$ Posted variant cstheory.stackexchange.com/questions/48491/…. $\endgroup$ – 1.. Feb 26 at 6:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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