Description
1. [2 marks] In words, which class of problems does PSPACE characterize?
2. [4 marks] Show that PSPACE is closed under the concatenation and star operations.
3. [4 marks] Prove that NP ⊆ PSPACE by giving a polynomial-space algorithm for simulating an NP machine
(use Theorem 7.20 for this, which says a language is in NP iff it is decided by a non-deterministic polynomial
time Turing machine).
4. [2 marks] Why is Savitch’s theorem surprising, given our study of P versus NP?
5. [14 marks] This question studies the proof of Savitch’s theorem. You may assume the TM M in the proof can
compute function f(n) in the proof in O(f(n)) space.
(a) [2 marks] In words, give a high-level overview of how the proof of Savitch’s theorem works.
(b) [6 marks] The CANYIELD procedure in the proof has 6 steps: Describe in a sentence or two the purpose
of each step.
(c) [2 marks] Why does the machine M in the proof correctly simulate the NTM N?
(d) [4 marks] Why does M use O(f
2
(n)) space?
1
