Questions: Space Complexity: PSPACE, L, and NL

Question 1

Savitch's theorem shows NPSPACE = PSPACE. Why doesn't the analogous argument collapse NP to P?

• A. Space is reusable across computation steps, but time is not
• B. Savitch's theorem is incorrect for time complexity
• C. NP and P are equal but the proof has not been found
• D. Space is always larger than time so the theorem trivially applies to time too

Answer: (A)

Space is reusable: a Turing machine can overwrite tape cells and use them again in later steps. Savitch's simulation exploits this to recursively reuse space, squashing nondeterministic S(n) space into deterministic O(S(n)²) space. Time is strictly sequential — each step is consumed once and cannot be shared. A nondeterministic path of length t requires t distinct time steps, so the recursive technique does not transfer.

Question 2

A problem in PSPACE can generally be solved in polynomial time.

• T. True
• F. False

Answer: False

PSPACE contains problems that may require exponential time even though they use only polynomial space. PSPACE-complete problems like QBF (Quantified Boolean Formula satisfiability) are believed to require super-polynomial time. The space bound restricts memory usage, not the number of computation steps, which can be exponentially large.

Question 3

What is the defining resource restriction for the class L (logarithmic space), and why is O(log n) bits sufficient to reason about positions in the input?

Model answer: L allows only O(log n) bits on the working tape (the input is read-only and not counted). This is enough to store a constant number of integer indices into the input, since any position 0 to n-1 requires at most log₂ n bits to represent.

The key insight is that O(log n) bits can encode any index into a length-n input. This means an L-machine can maintain pointers to positions in the input and do pointer arithmetic, even though it cannot copy the input. Graph reachability (STCON) lies in NL because a nondeterministic machine only needs to store the current node (one index) as it guesses a path from s to t.