## ← 10-13 Step 1

• 1 Follower
• 17 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=xTorHJShKcI" data-team="udacity"></div> ``` 1 Language

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.