Editing Complexity class (section)

===Savitch's theorem===
{{Main|Savitch's theorem}}
Savitch's theorem establishes the relationship between deterministic and nondetermistic space resources. It shows that if a nondeterministic Turing machine can solve a problem using <math>f(n)</math> space, then a deterministic Turing machine can solve the same problem in <math>f(n)^2</math> space, i.e. in the square of the space. Formally, Savitch's theorem states that for any <math>f(n) > n </math>,{{sfn|Lee|2014}}

:<math>\mathsf{NSPACE}\left(f\left(n\right)\right) \subseteq \mathsf{DSPACE}\left(f\left(n\right)^2\right).</math>

Important corollaries of Savitch's theorem are that '''PSPACE''' = '''NPSPACE''' (since the square of a polynomial is still a polynomial) and '''EXPSPACE''' = '''NEXPSPACE''' (since the square of an exponential is still an exponential).

These relationships answer fundamental questions about the power of nondeterminism compared to determinism. Specifically, Savitch's theorem shows that any problem that a nondeterministic Turing machine can solve in polynomial space, a deterministic Turing machine can also solve in polynomial space. Similarly, any problem that a nondeterministic Turing machine can solve in exponential space, a deterministic Turing machine can also solve in exponential space.