# 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 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

[edit | edit source]Savitch's theorem tells us that any problem that can be solved by a non-deterministic Turing machine in space can also be solved by a deterministic Turing machine in the square of that space (), provided that is of a greater or equal order than .

In formulas:

- If ,

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

because logarithmic space is affected by power increases.

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

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.