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.

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

1 Answer 1

Reset to default
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)$.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.