Reading: Chapter 5, pages 107-116 and Chapter 7, pages 145-160
Problems :
1. Prove that P is not contained in DTIME (nk), for any fixed natural number k.
2, Prove that if NSPACE(n) is a subset of P then PSPACE = NP.
3. Page 121, problem 5.15
4. Prove that NSPACE (2 n ) is properly contained in DSPACE (2 (n 2 ) ).
5. Prove Cor. 5.15 on page 111.
6. Page 143, problem 6.20
(You may use the fact here that SAT is NP-complete.)