# 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

- Prove that A
_{TM} is NP-hard.
- Sipser's text problem 7.17 page 272.
- Sipser's text problem 7.21 page 273.
- Sipser's text problem 7.28 page 274.
- Sipser's text problem 7.33 page 274.
- (Bonus) Sipser's text problem 7.25 page 274. (Note 1
^{t} is
a string of t 1's. You do NOT need the Cook-Levin Theorem to answer this
question.)
- (Bonus) Sipser's text problem 7.37 page 275.