Editing Complexity class (section)

====PSPACE and NPSPACE====
{{Main|PSPACE (complexity)}}
The complexity classes '''PSPACE''' and '''NPSPACE''' are the space analogues to '''[[P (complexity) | P]]''' and '''[[NP (complexity) | NP]]'''. That is, '''PSPACE''' is the class of problems solvable in polynomial space by a deterministic Turing machine and '''NPSPACE''' is the class of problems solvable in polynomial space by a nondeterministic Turing machine. More formally,
:<math>\mathsf{PSPACE} = \bigcup_{k\in\mathbb{N}} \mathsf{DSPACE}(n^k)</math>
:<math>\mathsf{NPSPACE} = \bigcup_{k\in\mathbb{N}} \mathsf{NSPACE}(n^k)</math>

While it is not known whether '''P'''='''NP''', [[Savitch's theorem ]] famously showed that '''PSPACE'''='''NPSPACE'''. It is also known that <math>\mathsf{P} \subseteq \mathsf{PSPACE}</math>, which follows intuitively from the fact that, since writing to a cell on a Turing machine's tape is defined as taking one unit of time, a Turing machine operating in polynomial time can only write to polynomially many cells. It is suspected that '''P''' is strictly smaller than '''PSPACE''', but this has not been proven.