Editing Complexity class (section)

==Relationships between complexity classes==

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

===Hierarchy theorems===
{{main article|Time hierarchy theorem|Space hierarchy theorem}}
By definition of '''DTIME''', it follows that <math>\mathsf{DTIME}(n^{k_1})</math> is contained in <math>\mathsf{DTIME}(n^{k_2})</math> if <math>k_1 \leq k_2 </math>, since <math>O(n^{k_1}) \subseteq O(n^{k_2})</math> if <math>k_1 \leq k_2</math>. However, this definition gives no indication of whether this inclusion is strict. For time and space requirements, the conditions under which the inclusion is strict are given by the time and space hierarchy theorems, respectively. They are called hierarchy theorems because they induce a proper hierarchy on the classes defined by constraining the respective resources. The hierarchy theorems enable one to make quantitative statements about how much more additional time or space is needed in order to increase the number of problems that can be solved.

The [[time hierarchy theorem]] states that
:<math>\mathsf{DTIME}\big(f(n) \big) \subsetneq \mathsf{DTIME} \big(f(n) \sdot \log^{2}(f(n)) \big)</math>.

The [[space hierarchy theorem]] states that
:<math>\mathsf{DSPACE}\big(f(n)\big) \subsetneq \mathsf{DSPACE} \big(f(n) \sdot \log(f(n)) \big)</math>.

The time and space hierarchy theorems form the basis for most separation results of complexity classes. For instance, the time hierarchy theorem establishes that '''P''' is strictly contained in '''EXPTIME''', and the space hierarchy theorem establishes that '''L''' is strictly contained in '''PSPACE'''.