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