Savitch's theorem proves PSPACE = NPSPACE. Why doesn't the same argument prove P = NP?
AThe theorem only applies to space resources — time cannot be reused the way space can, so the argument breaks down for time
BSavitch's theorem only applies to polynomial bounds, and NP uses exponential time
CNondeterministic space machines are a fundamentally different model than nondeterministic time machines
DSavitch's theorem requires the computation to be deterministic, which P already satisfies by definition
The key insight of Savitch's theorem is that space can be reused: a deterministic machine can simulate nondeterminism by exploring each branch sequentially, reusing the same polynomial memory for each branch. Time cannot be reused — once a time step passes, it's gone. Simulating nondeterminism deterministically in time requires storing or re-running all branches, which can cost exponential time. This asymmetry between space and time is why PSPACE = NPSPACE is proven while P vs NP remains open.
Question 2 Multiple Choice
Why is evaluating game positions (like generalized chess on an n×n board) typically PSPACE-complete rather than NP-complete?
AGame trees are too large to store in polynomial space, requiring exponential space
BChess positions require exponential time to evaluate but only polynomial space, which is the definition of PSPACE-complete
CDetermining whether a player has a winning strategy requires reasoning over all possible opponent responses to all possible moves — an alternating quantifier structure that exceeds what a single existential witness can capture
DNP problems cannot have game-theoretic formulations because games require interaction between players
NP is characterized by problems where you can verify a solution with a single existential witness ('there exists a satisfying assignment'). Games require alternating quantifiers: 'there exists a move such that for all opponent moves, there exists a reply such that...' This alternation of ∃ and ∀ is exactly the structure of TQBF (True Quantified Boolean Formulas), the canonical PSPACE-complete problem. The depth of this alternation makes game evaluation strictly harder than NP (assuming PSPACE ≠ NP), since no single witness can certify a winning strategy against all possible opponents.
Question 3 True / False
A polynomial-space machine can, in principle, run for exponential time without contradiction, because it can cycle through exponentially many distinct configurations before repeating a state.
TTrue
FFalse
Answer: True
A machine with p(n) tape cells can be in at most 2^p(n) distinct configurations (combining all possible tape contents, head positions, and states). A polynomial-space machine therefore has exponentially many configurations before any state must repeat. By the halting argument, a machine that hasn't halted and hasn't repeated a configuration will halt within this exponential bound. This is why PSPACE ⊆ EXPTIME: polynomial space implies exponential time, but not vice versa.
Question 4 True / False
We have proven that PSPACE is strictly larger than NP — that there exist problems in PSPACE that are not in NP.
TTrue
FFalse
Answer: False
This is unproven. We know NP ⊆ PSPACE (every NP problem can be solved in polynomial space by trying all certificates), and we believe the containment is strict, but no proof exists. We cannot even prove P ≠ NP, which is a weaker separation. The only known strict separation in this region is P ≠ EXPTIME (from the time hierarchy theorem), which guarantees that at least one of the containments P ⊆ NP ⊆ PSPACE ⊆ EXPTIME is strict — but we don't know which ones.
Question 5 Short Answer
Why can a deterministic machine solve any NPSPACE problem using only polynomial space (Savitch's theorem), while the analogous argument for time — that any NP problem can be solved deterministically in polynomial time — remains unproven?
Think about your answer, then reveal below.
Model answer: Space can be reused, but time cannot. To simulate nondeterminism, a deterministic machine must explore all nondeterministic branches. If we're counting space, we can explore each branch one at a time, reusing the same polynomial memory for each branch — we just need to keep track of where we are in the search. The total space remains polynomial, though the time required may be exponential. If we're counting time, exploring all branches deterministically requires running through each one, and the number of branches may be exponential — we can't 'reuse' the time steps already consumed.
This asymmetry reflects a deep structural difference between space and time as computational resources. Space is a shared pool that can be reclaimed after a branch is explored; time is a one-way sequence of irreversible steps. Savitch's theorem exploits this by framing reachability as a space-efficient recursion (can you reach the accepting configuration from the start in 2^k steps?) that reuses space at each recursive call.