0:00:00.000,0:00:03.850
So now that we have shown how shortest tour can be stated as a decision problem,

0:00:03.850,0:00:06.350
we still need to show that that problem is in NP,

0:00:06.350,0:00:09.840
and for shortest tour, while it's not really that difficult,

0:00:09.840,0:00:13.410
but it's actually a little bit of a hassle, so let's do another quiz here.

0:00:13.410,0:00:15.950
Why is shortest tour in NP?

0:00:15.950,0:00:18.720
So basically the question is: If we have nondeterminism,

0:00:18.720,0:00:21.600
why can shortest tour then be solved in polynomial time?

0:00:21.600,0:00:26.640
Is it because we can use nondeterminism to guess which vertices

0:00:26.640,0:00:28.180
to put into the shortest tour?

0:00:28.180,0:00:32.920
Is it because once once a shortest tour has been guessed using nondeterminism,

0:00:32.920,0:00:35.780
the length of that tour can be checked in polynomial time?

0:00:35.780,0:00:37.960
Is it because nondeterminism can guess a shortest tour,

0:00:37.960,0:00:43.320
and by that I mean that we can use the better function to guess the tour here,

0:00:43.320,0:00:45.440
so you would have something like this:

0:00:45.440,0:00:50.480
if better visit vertex A, else visit another vertex next.

0:00:50.480,0:00:54.390
Or, do we even have to show this? Because, actually, it's quite obvious.

0:00:54.390,9:59:59.000
So, more than one can be correct. Please tell me which ones are.