# COT 6421 - Homework 4

### Due Monday, March 28

Read chapter 7 of Sipser and solve the following problems.
- 7.3 [A routine application of Euclid's algorithm.]
- 7.12 [Asks for a fast exponentiation algorithm; such algorithms
are crucial for RSA cryptography.]
- 7.17 [A simple observation about polynomial-time mapping reducibility.]
- 7.19 [A simple NP-completeness proof.]
- 7.25 [This problem shows that the Cook-Levin theorem is significant not
because it shows that NP-complete languages exist, but because it shows
that
*natural* languages (like *SAT*) can be NP-complete.]
- 7.29 [This problem, like 7.28 and 7.30, shows that the assumption that
P=NP implies the existence of efficient algorithms not only for
*decision* problems, but for many *search* and
*optimization* problems as well.]

Back to