1 00:00:00,000 --> 00:00:03,850 So now that we have shown how shortest tour can be stated as a decision problem, 2 00:00:03,850 --> 00:00:06,350 we still need to show that that problem is in NP, 3 00:00:06,350 --> 00:00:09,840 and for shortest tour, while it's not really that difficult, 4 00:00:09,840 --> 00:00:13,410 but it's actually a little bit of a hassle, so let's do another quiz here. 5 00:00:13,410 --> 00:00:15,950 Why is shortest tour in NP? 6 00:00:15,950 --> 00:00:18,720 So basically the question is: If we have nondeterminism, 7 00:00:18,720 --> 00:00:21,600 why can shortest tour then be solved in polynomial time? 8 00:00:21,600 --> 00:00:26,640 Is it because we can use nondeterminism to guess which vertices 9 00:00:26,640 --> 00:00:28,180 to put into the shortest tour? 10 00:00:28,180 --> 00:00:32,920 Is it because once once a shortest tour has been guessed using nondeterminism, 11 00:00:32,920 --> 00:00:35,780 the length of that tour can be checked in polynomial time? 12 00:00:35,780 --> 00:00:37,960 Is it because nondeterminism can guess a shortest tour, 13 00:00:37,960 --> 00:00:43,320 and by that I mean that we can use the better function to guess the tour here, 14 00:00:43,320 --> 00:00:45,440 so you would have something like this: 15 00:00:45,440 --> 00:00:50,480 if better visit vertex A, else visit another vertex next. 16 00:00:50,480 --> 00:00:54,390 Or, do we even have to show this? Because, actually, it's quite obvious. 17 00:00:54,390 --> 99:59:59,999 So, more than one can be correct. Please tell me which ones are.