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