Savitch's theorem proves that PSPACE = NPSPACE.
Why the same theorem doesn't prove that NL = L?
Tell me more
×
Mathematics Stack Exchange is a question and answer site for
people studying math at any level and professionals in related fields. It's 100% free, no registration required.
|
|
|||||||||||
|
|
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. |
|||
|
|