CSEP 590TU Assignment #5
Autumn 2003

Due: Wednesday, Nov 5, 2003.

Read sections 7.4-5 and 9.3 of Sipser's text. We will use section 9.3 for the proof of the Cook-Levin theorem rather than the proof in section 7.4

Problems

  1. Prove that ATM is NP-hard.

  2. Sipser's text problem 7.17 page 272.

  3. Sipser's text problem 7.21 page 273.

  4. Sipser's text problem 7.28 page 274.

  5. Sipser's text problem 7.33 page 274.

  6. (Bonus) Sipser's text problem 7.25 page 274. (Note 1t is a string of t 1's. You do NOT need the Cook-Levin Theorem to answer this question.)

  7. (Bonus) Sipser's text problem 7.37 page 275.