Introduction to Complexity Theory/Space Complexity and Savitch's Theorem

From Wikiversity
Jump to navigation Jump to search

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.