P vs PSPACE Problem

Field: Complexity Theory
Importance: ⭐️⭐️⭐️⭐️
Reward: No formal prize, but solving it would be groundbreaking

Problem Statement

Is every problem that can be solved with polynomial space also solvable in polynomial time?

That is, does P = PSPACE?

This question compares the class P (problems solvable in polynomial time) to PSPACE (problems solvable in polynomial space), and asks whether the ability to use more time (but the same amount of memory) gives us fundamentally more computational power.

Historical Background

While P vs NP tends to steal the spotlight, P vs PSPACE is just as deep and perhaps more fundamental. The complexity class PSPACE was formally introduced in the early 1970s, building on the foundational work in Turing machines and space-bounded computation.

Notable Progress:

  • 1970s: The hierarchy of time and space complexity classes is established. It’s proven that:

    • P ⊆ NP ⊆ PSPACE ⊆ EXP
    • And crucially, PSPACE=NPSPACE (by Savitch’s Theorem).

  • 1979: A landmark result by Chandra, Kozen, and Stockmeyer introduces alternating Turing machines, proving that: APTIME = PSPACE

Over time, problems like TQBF (True Quantified Boolean Formula) became canonical PSPACE-complete problems. Despite these insights, the P vs PSPACE question remains unresolved.

What Is Known

  • P ⊆ PSPACE: Any problem solvable in polynomial time can also be solved using polynomial space.

  • PSPACE-complete problems: These include logic games (like Generalized Chess, Go, TQBF), model checking, and some forms of automated reasoning.

  • No known separations: Although we believe P ≠ PSPACE, there is no proof. In fact, even P vs NP remains unresolved, and since P ⊆ NP ⊆ PSPACE, solving P vs PSPACE would imply a solution to P vs NP.

Why It Matters

Solving P vs PSPACE would reshape our understanding of space and time in computation:

  • Theoretical implications: It would clarify the power of space-bounded computation and could collapse or separate major parts of the complexity hierarchy.

  • Formal verification & logic: Many PSPACE-complete problems arise in logical systems, model checking, and AI planning.

  • Game theory and AI: Determining the complexity of perfect-play in games often falls into PSPACE. A proof that P = PSPACE would change our understanding of algorithmic game-solving.

My Thoughts

To me, P vs PSPACE is the silent giant of complexity theory. It asks: Does having more memory (but not necessarily more time) give us fundamentally more computational power?

Most researchers believe that P ≠ PSPACE and for good reason. Many PSPACE-complete problems involve inherently deeper reasoning steps, such as evaluating all branches of a game tree or verifying fully quantified formulas. These don’t seem reducible to a fast, shallow process.

Yet there’s an interesting result in Savitch’s Theorem, which shows that nondeterministic polynomial space is no more powerful than deterministic space. This equivalence inspires hope that perhaps time and space, too, could converge under some surprising model or construction.

Whether P = PSPACE or not, exploring this boundary has already led to breakthroughs like:

  • Alternation and interactive proofs
  • Space-bounded logic
  • Circuit complexity and hierarchy theorems

Even if we never solve it, chasing the answer continues to enrich computer science.

References