﻿[Script Info] Title: [Events] Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text Dialogue: 0,0:00:00.00,0:00:03.85,Default,,0000,0000,0000,,So now that we have shown how shortest tour can be stated as a decision problem, Dialogue: 0,0:00:03.85,0:00:06.35,Default,,0000,0000,0000,,we still need to show that that problem is in NP, Dialogue: 0,0:00:06.35,0:00:09.84,Default,,0000,0000,0000,,and for shortest tour, while it's not really that difficult, Dialogue: 0,0:00:09.84,0:00:13.41,Default,,0000,0000,0000,,but it's actually a little bit of a hassle, so let's do another quiz here. Dialogue: 0,0:00:13.41,0:00:15.95,Default,,0000,0000,0000,,Why is shortest tour in NP? Dialogue: 0,0:00:15.95,0:00:18.72,Default,,0000,0000,0000,,So basically the question is: If we have nondeterminism, Dialogue: 0,0:00:18.72,0:00:21.60,Default,,0000,0000,0000,,why can shortest tour then be solved in polynomial time? Dialogue: 0,0:00:21.60,0:00:26.64,Default,,0000,0000,0000,,Is it because we can use nondeterminism to guess which vertices Dialogue: 0,0:00:26.64,0:00:28.18,Default,,0000,0000,0000,,to put into the shortest tour? Dialogue: 0,0:00:28.18,0:00:32.92,Default,,0000,0000,0000,,Is it because once once a shortest tour has been guessed using nondeterminism, Dialogue: 0,0:00:32.92,0:00:35.78,Default,,0000,0000,0000,,the length of that tour can be checked in polynomial time? Dialogue: 0,0:00:35.78,0:00:37.96,Default,,0000,0000,0000,,Is it because nondeterminism can guess a shortest tour, Dialogue: 0,0:00:37.96,0:00:43.32,Default,,0000,0000,0000,,and by that I mean that we can use the better function to guess the tour here, Dialogue: 0,0:00:43.32,0:00:45.44,Default,,0000,0000,0000,,so you would have something like this: Dialogue: 0,0:00:45.44,0:00:50.48,Default,,0000,0000,0000,,if better visit vertex A, else visit another vertex next. Dialogue: 0,0:00:50.48,0:00:54.39,Default,,0000,0000,0000,,Or, do we even have to show this? Because, actually, it's quite obvious. Dialogue: 0,0:00:54.39,9:59:59.99,Default,,0000,0000,0000,,So, more than one can be correct. Please tell me which ones are.