# COT 6421 - Homework 5

### Due Wednesday, April 20

Finish reading chapter 7 of Sipser and solve the following problems.
- 7.28
- 7.30
- 7.32 [A technical detail regarding the proof of the Cook-Levin theorem.]
- 7.34 [A rather complex NP-completeness proof.]
- 7.36 [This problem shows that, unlike DFAs, NFAs cannot be minimized
efficiently unless P=NP.]
- 7.37 [This problem shows that the satisfiability problem is efficiently
solvable for 2CNF formulas, unlike for 3CNF formulas.]

Back to