CSE 431 Assignment #6
Spring 2003

Due: Friday, May 23, 2003.

Read section 9.3 of Sipser's text. Finish reading chapter 7 of Sipser's text.

Problems

  1. Prove that ATM is NP-hard.

  2. Problem 7.17 page 272.

  3. Problem 7.21 page 272.

  4. Problem 7.29 page 274.

  5. Problem 7.33 page 274.

  6. (Bonus) Problem 7.36 page 275.