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.