CSE 531 Assignment #4
Autumn 1999

Due: Tuesday, November 23, 1999.

Problems from Sipser's text:

1. Problems 7.6 and 7.13

2. Problems 7.7 and 7.14

3. page 272, Problem 7.12

4. page 272, Problem 7.17

5. In the proof of Theorem 7.29, the statement is made that polynomial time reductions compose. Give a precise proof of this statement.

6. page 274, Problem 7.25

7. page 274, Problem 7.28