Editing PSPACE

{{Short description|Set of decision problems}}
{{redirect|Polynomial space|spaces of polynomials|Polynomial ring}}
[[Image:Complexity-classes-polynomial.svg|thumb|Inclusions of complexity classes including [[P (complexity)|P]], [[NP (complexity)|NP]], [[co-NP]], [[BPP (complexity)|BPP]], [[P/poly]], [[PH (complexity)|PH]], and [[PSPACE]]]]
{{unsolved|computer science|{{tmath|\mathsf{P \overset{?}{{=}} PSPACE} }}}}
In [[computational complexity theory]], '''PSPACE''' is the set of all [[decision problem]]s that can be solved by a [[Turing machine]] using a [[polynomial]] [[Space complexity|amount of space]].

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

== Relation among other classes ==
[[Image:Complexity subsets pspace.svg|300px|thumb|right|A representation of the relation among complexity classes]]
The following relations are known between PSPACE and the complexity classes [[NL (complexity)|NL]], [[P (complexity)|P]], [[NP (complexity)|NP]], [[PH (complexity)|PH]], [[EXPTIME]] and [[EXPSPACE]] (we use here <math>\subset</math> to denote strict containment, meaning a proper subset, whereas <math>\subseteq</math> includes the possibility that the two sets are the same):

:<math>\begin{array}{l}
\mathsf{NL \subseteq P \subseteq NP \subseteq PH \subseteq PSPACE}\\
\mathsf{PSPACE \subseteq EXPTIME \subseteq EXPSPACE}\\
\mathsf{NL \subset PSPACE \subset EXPSPACE}\\
\mathsf{P\subset EXPTIME}\end{array}</math>

From the third line, it follows that both in the first and in the second line, at least one of the set containments must be strict, but it is not known which.  It is widely suspected that all are strict.

The containments in the third line are both known to be strict.  The first follows from direct diagonalization (the [[space hierarchy theorem]], NL ⊂ NPSPACE) and the fact that PSPACE {{=}} NPSPACE via [[Savitch's theorem]].  The second follows simply from the space hierarchy theorem.

The hardest problems in PSPACE are the PSPACE-complete problems.  See [[PSPACE-complete]] for examples of problems that are suspected to be in PSPACE but not in NP.

== Closure properties ==
The class PSPACE is closed under operations [[Union (set theory)|union]], [[Complement (set theory)|complementation]], and [[Kleene star]].

== Other characterizations ==
An alternative characterization of PSPACE is the set of problems decidable by an [[alternating Turing machine]] in polynomial time, sometimes called APTIME or just AP.<ref name=AB100>Arora & Barak (2009) p.100</ref>

A logical characterization of PSPACE from [[descriptive complexity]] theory is that it is the set of problems expressible in [[second-order logic]] with the addition of a [[transitive closure]] operator. A full transitive closure is not needed; a commutative transitive closure and even weaker forms suffice. It is the addition of this operator that (possibly) distinguishes PSPACE from [[PH (complexity)|PH]].

A major result of complexity theory is that PSPACE can be characterized as all the languages recognizable by a particular [[interactive proof system]], the one defining the class [[IP (complexity)|IP]]. In this system, there is an all-powerful prover trying to convince a randomized polynomial-time verifier that a string is in the language. It should be able to convince the verifier with high probability if the string is in the language, but should not be able to convince it except with low probability if the string is not in the language.

PSPACE can be characterized as the quantum complexity class [[QIP (complexity)|QIP]].<ref>{{cite arXiv|title=QIP = PSPACE|author1=Rahul Jain|author2=Zhengfeng Ji|author3=Sarvagya Upadhyay|author4-link=John Watrous (computer scientist)|author4=John Watrous|eprint=0907.4737|date=July 2009|class=quant-ph}}</ref>

PSPACE is also equal to P<sub>CTC</sub>, problems solvable by classical computers using [[closed timelike curve]]s,<ref>{{cite journal|author=S. Aaronson | arxiv=quant-ph/0502072| title= NP-complete problems and physical reality |journal=SIGACT News|date=March 2005| doi=10.1145/1052796.1052804|bibcode=2005quant.ph..2072A| s2cid=18759797}}.</ref> as well as to BQP<sub>CTC</sub>, problems solvable by [[quantum computer]]s using closed timelike curves.<ref>{{cite journal | doi=10.1098/rspa.2008.0350|bibcode = 2009RSPSA.465..631A | title=Closed timelike curves make quantum and classical computing equivalent | year=2009 | last1=Watrous | first1=John | last2=Aaronson | first2=Scott | journal=Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences | volume=465 | issue=2102 | pages=631 |arxiv = 0808.2669 |s2cid = 745646 }}</ref>

== PSPACE-completeness ==
{{main|PSPACE-complete}}
A language ''B'' is ''[[PSPACE-complete]]'' if it is in PSPACE and it is PSPACE-hard, which means for all ''A'' ∈ PSPACE, <math>A \leq_\text{P} B</math>, where <math>A \leq_\text{P} B</math> means that there is a [[polynomial-time many-one reduction]] from ''A'' to ''B''. PSPACE-complete problems are of great importance to studying PSPACE problems because they represent the most difficult problems in PSPACE. Finding a simple solution to a PSPACE-complete problem would mean we have a simple solution to all other problems in PSPACE because all PSPACE problems could be reduced to a PSPACE-complete problem.<ref name=AB83>Arora & Barak (2009) p.83</ref>

An example of a PSPACE-complete problem is the [[quantified Boolean formula problem]] (usually abbreviated to '''QBF''' or '''TQBF'''; the '''T''' stands for "true").<ref name=AB83/>

== Notes ==
{{reflist}}

== References ==
* {{cite book | zbl=1193.68112 | last1=Arora | first1=Sanjeev | author-link1=Sanjeev Arora | last2=Barak | first2=Boaz | title=Computational complexity. A modern approach | publisher=[[Cambridge University Press]] | year=2009 | isbn=978-0-521-42426-4 }}

==Further reading==
* {{cite book|author-link = Christos Papadimitriou | first=Christos | last=Papadimitriou | year = 1993 | title = Computational Complexity | publisher = Addison Wesley | edition = 1st | isbn = 0-201-53082-1}} Chapter 19: Polynomial space, pp.&nbsp;455–490.
* {{cite book| first = Michael | last=Sipser | author-link = Michael Sipser | year = 2006 | title = Introduction to the Theory of Computation | publisher = Thomson Course Technology| edition = 2nd | isbn = 0-534-95097-3}} Chapter 8: Space Complexity
* {{CZoo|PSPACE|P#pspace}}

{{ComplexityClasses}}

{{DEFAULTSORT:Pspace}}
[[Category:Complexity classes]]