Editing PSPACE (section)

== Formal definition ==
If we denote by SPACE(''f''(''n'')), the set of all problems that can be solved by [[Turing machines]] using ''O''(''f''(''n'')) space for some function ''f'' of the input size ''n'', then we can define PSPACE formally as<ref name=AB81>Arora & Barak (2009) p.81</ref>

:<math>\mathsf{PSPACE} = \bigcup_{k\in\mathbb{N}} \mathsf{SPACE}(n^k). </math>

It turns out that allowing the Turing machine to be [[Nondeterministic algorithm|nondeterministic]] does not add any extra power.  Because of [[Savitch's theorem]],<ref name=AB85>Arora & Barak (2009) p.85</ref> NPSPACE is equivalent to PSPACE, essentially because a deterministic Turing machine can simulate a [[nondeterministic Turing machine]] without needing much more space (even though [[P versus NP problem|it may use much more time]]).<ref name=AB86>Arora & Barak (2009) p.86</ref>  Also, the [[Complement (complexity)|complements]] of all problems in PSPACE are also in PSPACE, meaning that co-PSPACE {{=}} PSPACE.<ref>{{cite book|title=Randomized Algorithms|first1=Rajeev|last1=Motwani|author1-link=Rajeev Motwani|first2=Prabhakar|last2=Raghavan|author2-link=Prabhakar Raghavan|publisher=Cambridge University Press|year=1995|isbn=9780521474658|page=20|url=https://books.google.com/books?id=QKVY4mDivBEC&pg=PA20}}</ref>