# 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 ${\displaystyle 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 ${\displaystyle f\left(n\right)}$  space can also be solved by a deterministic Turing machine in the square of that space (${\displaystyle f^{2}\left(n\right)}$ ), provided that ${\displaystyle f\left(n\right)}$  is of a greater or equal order than ${\displaystyle \log \left(n\right)}$ .

In formulas:

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

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

${\displaystyle NL\subseteq L^{2}}$

because logarithmic space is affected by power increases.

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

${\displaystyle {\mathcal {PSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathcal {DSPACE}}\left(n^{k}\right)}$
${\displaystyle {\mathcal {NPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathcal {NSPACE}}\left(n^{k}\right)}$
${\displaystyle \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

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

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