Unsolved problem in computer science

⁠${\displaystyle \mathsf{P}\stackrel{\mathsf{?}}{\mathsf{=}}\mathsf{P}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}}$⁠

More unsolved problems in computer science

Incomputational complexity theory,PSPACE is the set of alldecision problems that can be solved by aTuring machine using apolynomialamount of space.

If we denote by SPACE(f(n)), the set of all problems that can be solved byTuring machines usingO(f(n)) space for some functionf of the input sizen, then we can define PSPACE formally as^[1]

${\displaystyle \mathsf{P}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}=\bigcup _{k\in \mathbb{N}}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}(n^k).}$

It turns out that allowing the Turing machine to benondeterministic does not add any extra power. Because ofSavitch's theorem,^[2] NPSPACE is equivalent to PSPACE, essentially because a deterministic Turing machine can simulate anondeterministic Turing machine without needing much more space (even thoughit may use much more time).^[3] Also, thecomplements of all problems in PSPACE are also in PSPACE, meaning that co-PSPACE = PSPACE.^[4]

The following relations are known between PSPACE and the complexity classesNL,P,NP,PH,EXPTIME andEXPSPACE (we use here${\displaystyle \subset }$ to denote strict containment, meaning a proper subset, whereas${\displaystyle \subseteq }$ includes the possibility that the two sets are the same):

${\displaystyle \begin{array}{l}\mathsf{N}\mathsf{L}\subseteq \mathsf{P}\subseteq \mathsf{N}\mathsf{P}\subseteq \mathsf{P}\mathsf{H}\subseteq \mathsf{P}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}\\ \mathsf{P}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}\subseteq \mathsf{E}\mathsf{X}\mathsf{P}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}\subseteq \mathsf{E}\mathsf{X}\mathsf{P}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}\\ \mathsf{N}\mathsf{L}\subset \mathsf{P}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}\subset \mathsf{E}\mathsf{X}\mathsf{P}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}\\ \mathsf{P}\subset \mathsf{E}\mathsf{X}\mathsf{P}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}\end{array}}$

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 (thespace hierarchy theorem, NL ⊂ NPSPACE) and the fact that PSPACE = NPSPACE viaSavitch's theorem. The second follows simply from the space hierarchy theorem.

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

The class PSPACE is closed under operationsunion,complementation, andKleene star.

An alternative characterization of PSPACE is the set of problems decidable by analternating Turing machine in polynomial time, sometimes called APTIME or just AP.^[5]

A logical characterization of PSPACE fromdescriptive complexity theory is that it is the set of problems expressible insecond-order logic with the addition of atransitive 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 fromPH.

A major result of complexity theory is that PSPACE can be characterized as all the languages recognizable by a particularinteractive proof system, the one defining the classIP. 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 classQIP.^[6]

PSPACE is also equal to P_CTC, problems solvable by classical computers usingclosed timelike curves,^[7] as well as to BQP_CTC, problems solvable byquantum computers using closed timelike curves.^[8]

A languageB isPSPACE-complete if it is in PSPACE and it is PSPACE-hard, which means for allA ∈ PSPACE,${\displaystyle A{\le }_{\text{P}}B}$, where${\displaystyle A{\le }_{\text{P}}B}$ means that there is apolynomial-time many-one reduction fromA toB. 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.^[9]

An example of a PSPACE-complete problem is thequantified Boolean formula problem (usually abbreviated toQBF orTQBF; theT stands for "true").^[9]

• Arora, Sanjeev; Barak, Boaz (2009).Computational complexity. A modern approach.Cambridge University Press.ISBN 978-0-521-42426-4.Zbl 1193.68112.

• 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
• Williams, Ryan (2025-02-25). "Simulating Time With Square-Root Space".arXiv:2502.17779 [cs.CC].

• Complexity Zoo:PSPACE

• Complexity classes

• Articles with short description
• Short description is different from Wikidata