1
$\begingroup$

I'm trying to figure out if the following statements are true:

• Savitch’s theorem implies that $NSpace(\log n)$ = $DSpace(\log n)$.

• Savitch’s theorem implies that $NSpace(n^2)$ = $DSpace(n^4)$.

• Savitch’s theorem implies that $NExpSpace = ExpSpace$.

• Knowing that QBF validity is $PSpace$-hard, Savitch’s theorem implies that QBF validity is also $NPSpace$-hard.

I'm not entirely sure about how to go about solving the first 2. I know that the last two are true for sure, because Savitch's theorem implies that $PSPACE = NPSPACE$ and $EXPSPACE = NEXPSPACE$ as the square of a polynomial is a polynomial and the square of an exponential function is an exponential function. But I'm not sure about the first two.

$\endgroup$
1
  • $\begingroup$ Hi! I'm sorry, I'd forgotten to accept the answer. Yes, it was helpful thanks! $\endgroup$ May 15 at 17:20

1 Answer 1

1
$\begingroup$

For the first two, we do not know whether it is true or false.

  • It is not known whether $\text{NSpace}(\log n)$ = $\text{DSpace}(\log n)$, although Savitch’s theorem implies that $\text{NSpace}(\log n)\subseteq \text{DSpace}(\log^2 n)$.

  • It it not known whether $\text{NSpace}(n^2)$ = $\text{DSpace}(n^4)$, although Savitch’s theorem implies that $\text{NSpace}(n^2)\subseteq\text{DSpace}(n^4)$.

Or we could say that Savitch's theorem is not strong enough to determine whether $\text{NSpace}(\log n)$ = $\text{DSpace}(\log n)$ and whether $\text{NSpace}(n^2)$ = $\text{DSpace}(n^4)$ without further significant development in the complexity theory of compute science.

There are claims that $\text{NSpace}(\log n) \neq\text{DSpace}(\log n)$, such as corollary $1$ in this paper by Tianrong Lin. However, "$\text{L} = \text{NL}$ problem" is listed one of open problems in this Wikipedia page still. Here $\text{L}$ is $\text{DSpace}(\log n)$ and $\text{NL}$ is $\text{NSpace}(\log n)$.

$\endgroup$

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.