# Implications of Savitch's theorem

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.

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

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