Savitch's theorem states that NSPACE(f(n)) ⊆ DSPACE(f(n)²). What is the most important corollary of this theorem for polynomial space?
ANP = P, because nondeterminism provides no advantage for polynomial-bounded computations
BNPSPACE = PSPACE, because squaring a polynomial still yields a polynomial
CPSPACE ⊆ NP, because any polynomial-space computation can be verified nondeterministically
DL = NL, because squaring logarithm still gives a logarithm
Squaring a polynomial p(n) gives another polynomial p(n)², so NSPACE(p(n)) ⊆ DSPACE(p(n)²) places NPSPACE inside PSPACE — and since PSPACE ⊆ NPSPACE trivially, we get NPSPACE = PSPACE. This collapses nondeterministic and deterministic polynomial space together. Note that L and NL do NOT collapse under Savitch's theorem: squaring O(log n) gives O((log n)²) = O(log² n), which is a larger space class (DSPACE(log² n)), not O(log n) — so NL ⊆ DSPACE(log² n) but this doesn't prove NL = L.
Question 2 Multiple Choice
Why is PSPACE believed to be strictly larger than NP, even though NP ⊆ PSPACE?
ABecause PSPACE problems require exponential time, which cannot be verified in polynomial time
BBecause PSPACE-complete problems like TQBF involve alternating quantifiers (∀ and ∃), while NP problems involve only existential quantifiers, suggesting qualitatively harder structure
CBecause PSPACE is closed under complement and NP is not, proving they differ
DBecause Savitch's theorem shows PSPACE has strictly more computational power than any nondeterministic class
PSPACE-complete problems like TQBF (True Quantified Boolean Formulas) involve alternating universal and existential quantifiers, modeling adversarial two-player games. A witness for an NP problem is a short certificate that a verifier checks — one party's move. TQBF requires evaluating game trees where both players play optimally, which seems to require exploring an exponentially large space of play sequences. NP captures 'someone can demonstrate a solution exists'; PSPACE captures 'we can determine the winner regardless of what the opponent does.' The qualitative difference in problem structure strongly suggests strict containment, though it remains unproven.
Question 3 True / False
Savitch's theorem shows that nondeterminism provides no more than a quadratic advantage in space, unlike in time where nondeterminism might provide an exponential advantage.
TTrue
FFalse
Answer: True
Savitch's theorem establishes NSPACE(f(n)) ⊆ DSPACE(f(n)²) — nondeterminism adds at most a quadratic cost in space. This contrasts sharply with time: we do not know whether nondeterminism provides an exponential advantage in time (the P vs NP question), but if NP ≠ P, it would. Intuitively, space can be reused (old tape cells can be overwritten) while time cannot — a computation that guesses and checks can reuse its workspace for each guess. This reusability is why nondeterminism is less powerful in space than it might be in time.
Question 4 True / False
PSPACE is simply 'NP with more memory' — any NP problem can be efficiently solved using polynomial space.
TTrue
FFalse
Answer: False
While NP ⊆ PSPACE (every NP problem can be solved in polynomial space — just simulate the nondeterministic machine using polynomial space), PSPACE is believed to be strictly larger than NP. PSPACE contains problems — like evaluating game positions with alternating play (TQBF is PSPACE-complete) — that are thought to be qualitatively harder than any NP problem. The phrase 'more memory' misses the point: PSPACE captures problems where the key difficulty is exploring an adversarial search space, not merely finding a single certificate whose existence witnesses a 'yes' answer.
Question 5 Short Answer
In what ways does nondeterminism behave differently in space complexity than in time complexity, and what does Savitch's theorem tell us about this difference?
Think about your answer, then reveal below.
Model answer: In time complexity, nondeterminism may provide an exponential speedup — this is the unsolved P vs NP question. In space complexity, Savitch's theorem shows nondeterminism provides at most a quadratic advantage: NSPACE(f(n)) ⊆ DSPACE(f(n)²). The reason is that space is reusable: a deterministic machine can simulate nondeterministic reachability by recursively checking whether a configuration is reachable in 2^k steps (checking both halves of a midpoint), reusing the same workspace across recursive calls. This recursion depth is only log(f(n)) deep, so the space cost is f(n)·log(f(n)) or f(n)², not exponential. Time cannot be similarly reused because each computation step is consumed irreversibly.
The contrast highlights a fundamental difference between time and space as computational resources. Space is a renewable resource — the same cells can be overwritten — while time flows in one direction. This makes space amenable to compression via reuse in a way time is not, collapsing the nondeterministic and deterministic polynomial-space classes (NPSPACE = PSPACE) while leaving the analogous time question (NP =? P) open.