PSPACE
The complexity class of problems solvable using a polynomial amount of memory, even if that takes exponential time; contains P and NP.
As defined in 99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity
Where it comes up · 1
Most important claims · 3 of 3Search all claims for “PSPACE” →
- If polynomial time equaled polynomial space, then perfectly playing two-player games of perfect information like chess or Go — which can be solved with small memory by traversing the exponentially large game tree — would also become solvable in a small amount of time, yielding a super-efficient algorithm to play any such game perfectly, which is why we doubt P equals PSPACE.99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity
- Because P is contained in BQP which is contained in PSPACE, quantum computers can give at most an exponential running-time advantage over classical ones and cannot solve anything uncomputable like the halting problem; moreover, proving P is not equal to BQP would require proving P is not equal to PSPACE, explaining why a real-world quantum advantage cannot yet be proven.99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity
- Polynomial time (P) is contained in polynomial space (PSPACE), which is contained in exponential time, because a serial computer using N bits of memory can pass through at most 2-to-the-N states before halting or looping; we believe each containment is strict but have only proven that exponential time is strictly larger than polynomial time.99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity