﻿[Script Info] Title: [Events] Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text Dialogue: 0,0:00:00.00,0:00:01.63,Default,,0000,0000,0000,,And there are two correct answers here. Dialogue: 0,0:00:01.63,0:00:05.95,Default,,0000,0000,0000,,The first one is the simulation takes longer by a polynomial time factor. Dialogue: 0,0:00:05.95,0:00:08.92,Default,,0000,0000,0000,,Now, it's a bit difficult if you wanted to specify exactly Dialogue: 0,0:00:08.92,0:00:11.79,Default,,0000,0000,0000,,how much longer a simulation like this takes. Dialogue: 0,0:00:11.79,0:00:17.12,Default,,0000,0000,0000,,In my point of view, you would not even take polynomially longer but only a constant factor, Dialogue: 0,0:00:17.12,0:00:19.99,Default,,0000,0000,0000,,but polynomial is safe enough because in this course we're mostly Dialogue: 0,0:00:19.99,0:00:23.67,Default,,0000,0000,0000,,differentiating between polynomial and exponential running time. Dialogue: 0,0:00:23.67,0:00:28.14,Default,,0000,0000,0000,,Now, the reason why it only takes polynomial time longer is that, as I said before, Dialogue: 0,0:00:28.14,0:00:34.04,Default,,0000,0000,0000,,once we're in the certain line of code, this line of code specifies exactly what is going to happen next. Dialogue: 0,0:00:34.04,0:00:40.06,Default,,0000,0000,0000,,So it's mostly an overhead of simulating what this line here of code does, but as we said Dialogue: 0,0:00:40.06,0:00:44.96,Default,,0000,0000,0000,,when we specify the RAM model, each line here is a simple operations, so it takes constant Dialogue: 0,0:00:44.96,0:00:46.67,Default,,0000,0000,0000,,amount of time on the RAM. Dialogue: 0,0:00:46.67,0:00:52.41,Default,,0000,0000,0000,,I think it's fair to say that it will only take polynomially more time if you simulate what it does. Dialogue: 0,0:00:52.41,0:00:56.24,Default,,0000,0000,0000,,It doesn't do anything really complex. So the second answer here is wrong. Dialogue: 0,0:00:56.24,0:01:01.74,Default,,0000,0000,0000,,The simulation is also always correct because there's no involvement of randomness Dialogue: 0,0:01:01.74,0:01:03.42,Default,,0000,0000,0000,,or guessing and such. Dialogue: 0,0:01:03.42,0:01:06.47,Default,,0000,0000,0000,,So if the simulator is programmed correctly, we will always get Dialogue: 0,0:01:06.47,0:01:08.83,Default,,0000,0000,0000,,the same result that we would have originally gotten. Dialogue: 0,0:01:08.83,9:59:59.99,Default,,0000,0000,0000,,It only takes longer time.