English subtitles

← 10-15 Step 2

Get Embed Code
1 Language

Download

Showing Revision 1 created 10/03/2012 by Amara Bot.

  1. Now, before we actually do step two, let's have a brief review of what step two actually means.
  2. So, to show that shortest tour is NP-hard, which would then make it NP-complete,
  3. because we've already shown that it is in NP,
  4. what do we need to show?
  5. Do we need to show that the input for some NP-complete problem
  6. can be transformed into an input for shortest tour.
  7. And, of course, if this input here is a yes for this NP-complete problem,
  8. then it has to be yes for shortest tour here as well.
  9. If it's the no it's has to be a no.
  10. Or do we need to show that the input for shortest tour can be transformed
  11. into an input for some other NP-complete problem?
  12. Basically, I would like you to review here which direction these transformations work.
  13. Of course, we'll always make the assumption that the transformation is in polynomial time.