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

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.