English subtitles

← 10-13 Step 1

Get Embed Code
1 Language

Download

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

  1. So now that we have shown how shortest tour can be stated as a decision problem,
  2. we still need to show that that problem is in NP,
  3. and for shortest tour, while it's not really that difficult,
  4. but it's actually a little bit of a hassle, so let's do another quiz here.
  5. Why is shortest tour in NP?
  6. So basically the question is: If we have nondeterminism,
  7. why can shortest tour then be solved in polynomial time?
  8. Is it because we can use nondeterminism to guess which vertices
  9. to put into the shortest tour?
  10. Is it because once once a shortest tour has been guessed using nondeterminism,
  11. the length of that tour can be checked in polynomial time?
  12. Is it because nondeterminism can guess a shortest tour,
  13. and by that I mean that we can use the better function to guess the tour here,
  14. so you would have something like this:
  15. if better visit vertex A, else visit another vertex next.
  16. Or, do we even have to show this? Because, actually, it's quite obvious.
  17. So, more than one can be correct. Please tell me which ones are.