Questions: PSPACE and PSPACE-Completeness

Question 1

What is the key conceptual difference between SAT (an NP-complete problem) and TQBF (the canonical PSPACE-complete problem)?

• A. SAT uses Boolean formulas while TQBF uses arithmetic formulas — the difference is purely syntactic
• B. SAT asks whether some assignment satisfies the formula (one player, one move); TQBF asks whether a formula is true under all ∀-choices despite optimal ∃-choices (adversarial game, many moves)
• C. SAT is solvable in polynomial time; TQBF requires exponential time, placing it outside NP
• D. TQBF is just a generalization of SAT to longer formulas — if SAT were polynomial-time, so would TQBF

Answer: (B)

SAT is a one-player puzzle: find a single assignment that satisfies the formula. The certificate (the satisfying assignment) is polynomial in size and verifiable in polynomial time — that's what makes it NP. TQBF is an adversarial game between an existential player (∃) and a universal player (∀): does ∃ have a winning strategy no matter what ∀ does? Evaluating this requires exploring an exponentially large game tree where both players move optimally. No polynomial-size certificate exists for a 'yes' answer (you can't just exhibit one assignment), which is why TQBF is harder than NP under standard assumptions.

Question 2

Many combinatorial board games — generalized chess endgames, generalized Hex, generalized Go — are PSPACE-complete. What property of two-player perfect-information games connects them to PSPACE?

• A. These games have exponentially many board positions, placing them automatically in EXPTIME
• B. Determining the winner with perfect play requires evaluating an adversarial game tree with alternating ∀/∃ quantifiers over polynomial-length plays, which is exactly what PSPACE captures
• C. The games are PSPACE-complete because their rules can be encoded as a polynomial-space Turing machine computation
• D. All games with more than two players are automatically PSPACE-complete due to coordination complexity

Answer: (B)

PSPACE is the complexity class that captures 'who wins a perfect-information polynomial-length game?' The connection is direct: game trees with alternating moves are equivalent to formulas with alternating ∀/∃ quantifiers. Evaluating who wins from any position — assuming both players play optimally — requires exploring every branch of the game tree (the ∀-player's moves must all be considered; the ∃-player's best move must be found). For games with polynomial-length plays, this corresponds exactly to evaluating a quantified Boolean formula — TQBF — which is PSPACE-complete.

Question 3

PSPACE contains the entire polynomial hierarchy, including NP and co-NP.

• T. True
• F. False

Answer: True

The containment chain is: P ⊆ NP ⊆ PH ⊆ PSPACE ⊆ EXPTIME. Problems in NP can be solved by a nondeterministic polynomial-time machine, which uses only polynomial space (the accepting path has polynomial length, and you can verify it in polynomial space). By Savitch's theorem, NPSPACE = PSPACE, so nondeterministic polynomial space equals deterministic polynomial space. The entire polynomial hierarchy — which stratifies problems by alternation depth — collapses into PSPACE, which handles unbounded quantifier alternation. Whether these containments are strict (i.e., P ≠ NP ≠ PSPACE) is open, but PSPACE-complete problems are believed to be strictly harder than any level of PH.

Question 4

Since PSPACE problems are harder than NP problems, they require exponential space to solve.

• T. True
• F. False

Answer: False

PSPACE is defined as the class of problems solvable using only polynomial space — that is the definition, not a lower bound. A problem being PSPACE-complete means it is among the hardest problems in PSPACE, but all problems in PSPACE are solvable with polynomial space (though possibly exponential time). The 'harder than NP' comparison refers to computational difficulty in terms of what strategies are needed, not that more space is required. PSPACE-hard problems can often be solved by exhaustive game-tree search that reuses the same polynomial space stack — space is cheap, time is what blows up.

Question 5

Explain Savitch's theorem — that NPSPACE = PSPACE — and why this is surprising compared to what we believe about time complexity.

Model answer: Savitch's theorem says that nondeterminism buys at most a quadratic blowup in space: if a nondeterministic machine solves a problem in s(n) space, a deterministic machine can solve it in O(s(n)²) space. Applied to polynomial space: NPSPACE ⊆ PSPACE, so they are equal (since PSPACE ⊆ NPSPACE trivially). The proof uses recursive reachability: to check if a configuration C is reachable from C₀ in t steps, check if any intermediate configuration C_mid is reachable in t/2 steps from each endpoint — recursing to depth log(t). The recursion stack uses O(s·log t) space, which for polynomial s and polynomial t is still polynomial. This is surprising because with time, we strongly believe P ≠ NP — nondeterminism is conjectured to give an exponential advantage. With space, nondeterminism helps at most quadratically.

The contrast between time and space complexity is striking. For time, P ≠ NP is widely believed: nondeterminism is thought to give an exponential speedup for many problems. For space, nondeterminism barely helps: NPSPACE = PSPACE exactly. Intuitively, space can be reused across time steps in a way that time cannot be reused. A nondeterministic machine explores many paths, but deterministically you can verify reachability one configuration at a time, reusing the same space for each check. This reuse is what Savitch's algorithm exploits. It is one of the most elegant results in complexity theory and highlights that the properties of time and space as computational resources are fundamentally different.