Savitch's theorem proves that PSPACE = NPSPACE.
Why the same theorem doesn't prove that NL = L?
Asked
Active
Viewed 598 times
1
Rami
- 481
-
How would you prove a relationship in processing time based on relationship to space? – gt6989b Sep 19 '12 at 16:15
-
2@gt6989b- The classes L and NL are log space and nondeterministic log space, respectively. – templatetypedef Sep 19 '12 at 16:24
-
2btw, you can also post complexity theory questions on [cs.se]. – Kaveh Sep 26 '12 at 06:01
1 Answers
6
If we have a problem in $\mathsf{NSpace}(f)$, then by Savitch's theorem it is in $\mathsf{DSpace}(f^2)$, i.e. $\mathsf{NSpace}(f) \subseteq \mathsf{DSpace}(f^2)$.
If $f$ is a polynomial, then $f^2$ is a polynomial, so we get $\mathsf{NPSpace} \subseteq \mathsf{PSpace}$.
If $f$ is $\lg n$, then $f^2$ is $\lg^2 n$, therefore we only get $\mathsf{NL} \subseteq \mathsf{DSpace}(\lg^2 n)$, we do not get $\mathsf{NL} \subseteq \mathsf{DSpace}(\lg n) = \mathsf{L}$.
In other words, polynomials are closed under squaring, $O(\lg n)$ is not.
Kaveh
- 3,572