Introduction to Complexity Theory/Space Complexity and Savitch's Theorem

The space complexity of a problem describes the computational space needed to solve a particular problem on a particular Turing machine.

As with time complexity, for a constructible function $f(n)$ of the input length there exist two classes describing deterministic and non-deterministic space complexity, DSPACE(f(n)) and NSPACE(f(n)), respectively.

Savitch's Theorem

Savitch's theorem tells us that any problem that can be solved by a non-deterministic Turing machine in $f\left(n\right)$ space can also be solved by a deterministic Turing machine in the square of that space ($f^{2}\left(n\right)$), provided that $f\left(n\right)$ is of a greater or equal order than $\log \left(n\right)$.

In formulas:

If $f\left(n\right)\in \Omega \left(\log \left(n\right)\right)$, ${\mathcal {NSPACE}}\left(f\left(n\right)\right)\subseteq {\mathcal {DSPACE}}\left(f^{2}\left(n\right)\right)$

An immediate consequence that $L$, the class of decision problems solvable in deterministic logarithmic space and $NL$, the corresponding non-deterministic space class, are related as such:

$NL\subseteq L^{2}$

because logarithmic space is affected by power increases.

But what is the effect of this theorem on polynomial space?

${\mathcal {PSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathcal {DSPACE}}\left(n^{k}\right)$

${\mathcal {NPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathcal {NSPACE}}\left(n^{k}\right)$

$\forall k\in \mathbb {N} ,f\left(n\right)=n^{k}\therefore f\left(n\right)=O\left(f^{2}\left(n\right)\right)$

and as a result of that

${\mathcal {PSPACE}}={\mathcal {NPSPACE}}$,

meaning that non-deterministic polynomial space does not give us an advantage in solving problems over deterministic polynomial space.