Description
One of the goals of this course is to train you to be able to expand your education independently, given the tools
you’ve learned here. For this reason, your mini-project will consist of the following task.
First, please independently
read Sections 8.1 and 8.2 on Space Complexity. This will introduce you to the complexity class PSPACE and Savitch’s
theorem. Next, answer the following questions.
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