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 \mathrm{\Omega }(\log \left(n\right))$, $𝒩𝒮𝒫𝒜𝒞ℰ\left(f\left(n\right)\right)\subseteq 𝒟𝒮𝒫𝒜𝒞ℰ\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?

$𝒫𝒮𝒫𝒜𝒞ℰ=\bigcup _{k\in \mathbb{N}}𝒟𝒮𝒫𝒜𝒞ℰ\left(n^k\right)$

$𝒩𝒫𝒮𝒫𝒜𝒞ℰ=\bigcup _{k\in \mathbb{N}}𝒩𝒮𝒫𝒜𝒞ℰ\left(n^k\right)$

$\mathrm{\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

$𝒫𝒮𝒫𝒜𝒞ℰ=𝒩𝒫𝒮𝒫𝒜𝒞ℰ$,

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