Homework 13

Details

1. 7.4 (cancelled)
2. 7.5
3. 7.7
4. 7.8
5. 7.9
6. 7.12
7. 7.20
8. 7.22

• 7.7 is really easy--You essentially need to re-prove two exercises from chapter 3 (one which you did for homework, the other they provided a solution for) with the added requirement to show that the polynomial time requirement is satisfied.
• For 7.8, you should be able to determine that the algorithm runs in O(n⁴) time.
• 7.9 is really easy if you don't over think it.
• You have two choices for 7.12:
  1. Give a NTM that decides the language.
  2. Define a certificate for the problem and explain how it can be used to verify that the two graphs are isomorphic.
• For 7.20, you may use the result of exercise 7.18 if you think it helps.
• For 7.22, make sure you show that it is both NP and NP-Hard. For the latter part, reduce from SAT. For p in SAT, show that f(p) is in DOUBLE-SAT. Then show that if f(p) is in DOUBLE-SAT, then p has to be in SAT.