|
| Homework 13General Comments
- Problems are taken from the textbook unless otherwise noted.
- For full credit, provide context for each problem, show all calculations, and explain your work/answers.
- Numbers and/or algebra by themselves are not enough.
- You will lose a significant amount of credit if you do not show enough work/context for your answers.
- Precision is very important. You cannot skip steps, make guesses, or use flawed logic. Any of these things can lead to incorrect answers.
- Homework assignments must be very neatly written or typeset
(e.g. using Word or OpenOffice).
- You must indicate any assistance you had on an assignment as specified on the Policies page.
Details| Problem | Comments
|
|---|
| 7.7 | You only need to prove closure under union. This one is really easy--You essentially need to re-prove an exercise from chapter 3 (for which a solution is given) with the added requirement to show that the polynomial time requirement is satisfied.
| | 7.9 | This one is really easy if you don't over think it.
| | 7.20 | Make sure to answer both questions, and do so separately. You may use the result of exercise 7.18 if you think it helps.
| 7.12 | You have two choices:- Give a NTM that decides the language.
- Define a certificate for the problem and explain how it can be used to verify that the two graphs are isomorphic.
In both cases, you need to argue that they are polynomial-time. Notice that you only need to prove that it is NP, not that it is NP-complete.
| 7.21b | Make sure you show that it is both NP and NP-Hard. For the NP-Hard part, give a TM that computes the reduction and prove that it is indeed a reduction, and argue that it is a polynomial reduction. There is an easy reduction if you choose the right problem to reduce from. |
|
|
|