Course contentsShow
← Computer Science
Lesson 1895 of 2,87243. Complexity TheoryFree lesson

The Class PSPACE

Understanding problems solvable with polynomial space and the relationship between PSPACE, P, and NP.

The Class PSPACE

You'll learn: What PSPACE is and how it relates to the complexity classes P and NP you've already studied.

What is PSPACE?

PSPACE is the complexity class containing all decision problems that can be solved by a Turing machine using a polynomial amount of space (memory), regardless of how much time it takes. The key resource constraint here is space, not time.

For example, if a problem can be solved using O(n²) memory cells or O(n³) memory cells (where n is the input size), it belongs to PSPACE—even if the algorithm takes exponential time to run.

How PSPACE Relates to P and NP

Think of complexity classes as nested boxes:

  • P ⊆ NP ⊆ PSPACE: Everything solvable in polynomial time (P) is also solvable in polynomial space. Everything verifiable in polynomial time (NP) can also be solved in polynomial space by simply checking all possible certificates.

  • P ⊆ PSPACE ⊆ EXP: If you can solve a problem in polynomial space, you can solve it in exponential time (because you can only visit finitely many configurations with polynomial space). Since P is contained in EXP, PSPACE sits somewhere in between.

The exact relationships remain open questions: we don't know if P = PSPACE or if NP = PSPACE, though most researchers believe they're all distinct.

Why PSPACE Matters

PSPACE captures problems where you need to explore vast search spaces but can reuse memory cleverly—like game-playing scenarios where you evaluate positions recursively without storing every board state simultaneously.

Key Takeaway: PSPACE contains problems solvable with polynomial memory; it provably contains P and NP, and is contained in EXP, representing a fundamental tier in our hierarchy of computational difficulty.