# PSPACE

Open problem in computer science: |

In computational complexity theory, **PSPACE** is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.

## Contents

## Formal definition

If we denote by **SPACE**(*t*(*n*)), the set of all problems that can be solved by Turing machines using *O*(*t*(*n*)) space for some function *t* of the input size *n*, then we can define **PSPACE** formally as^{[1]}

**PSPACE** is a strict superset of the set of context-sensitive languages.

It turns out that allowing the Turing machine to be nondeterministic does not add any extra power. Because of Savitch's theorem,^{[2]} **NPSPACE** is equivalent to **PSPACE**, essentially because a deterministic Turing machine can simulate a non-deterministic Turing machine without needing much more space (even though it may use much more time).^{[3]} Also, the complements of all problems in **PSPACE** are also in **PSPACE**, meaning that **co-PSPACE** = **PSPACE**.

## Relation among other classes

The following relations are known between **PSPACE** and the complexity classes **NL**, **P**, **NP**, **PH**, **EXPTIME** and **EXPSPACE** (note that ⊊ is not the same as ⊈):

It is known that in the first and 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**.

## 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**.^{[4]}

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

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**. 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**.^{[5]}

**PSPACE** is also equal to **P _{CTC}**, problems solvable by classical computers using closed timelike curves,

^{[6]}as well as to

**BQP**, problems solvable by quantum computers using closed timelike curves.

_{CTC}^{[7]}

## PSPACE-completeness

A language *B* is *PSPACE-complete* if it is in **PSPACE** and it is PSPACE-hard, which means for all A ∈ **PSPACE**, A B, where A B 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.^{[8]}

An example of a **PSPACE**-complete problem is the quantified Boolean formula problem (usually abbreviated to **QBF** or **TQBF**; the **T** stands for "true").^{[8]}

## References

- ↑ Arora & Barak (2009) p.81
- ↑ Arora & Barak (2009) p.85
- ↑ Arora & Barak (2009) p.86
- ↑ Arora & Barak (2009) p.100
- ↑
**QIP**=**PSPACE**, Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous arXiv:0907.4737 (July 2009) - ↑ S. Aaronson, NP-complete problems and physical reality,
*SIGACT News*, March 2005. arXiv:quant-ph/0502072. - ↑ Watrous, John; Aaronson, Scott (2009). "Closed timelike curves make quantum and classical computing equivalent".
*Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences*.**465**(2102): 631. Bibcode:2009RSPSA.465..631A. arXiv:0808.2669 . doi:10.1098/rspa.2008.0350. - ↑
^{8.0}^{8.1}Arora & Barak (2009) p.83

- Arora, Sanjeev; Barak, Boaz (2009).
*Computational complexity. A modern approach*. Cambridge University Press. ISBN 978-0-521-42426-4. Zbl 1193.68112. - Sipser, Michael (1997).
*Introduction to the Theory of Computation*. PWS Publishing. ISBN 0-534-94728-X. Section 8.2–8.3 (The Class PSPACE, PSPACE-completeness), pp. 281–294. - Papadimitriou, Christos (1993).
*Computational Complexity*(1st ed.). Addison Wesley. ISBN 0-201-53082-1. Chapter 19: Polynomial space, pp. 455–490. - Sipser, Michael (2006).
*Introduction to the Theory of Computation*(2nd ed.). Thomson Course Technology. ISBN 0-534-95097-3. Chapter 8: Space Complexity