[Script Info]
Title:
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:04.43,Default,,0000,0000,0000,,And the answer here is that we end up with 2^n simulations,
Dialogue: 0,0:00:04.43,0:00:09.66,Default,,0000,0000,0000,,because each time that we encounter if-better we have to split into two possibilities
Dialogue: 0,0:00:09.66,0:00:14.68,Default,,0000,0000,0000,,and then the next time, we encounter if-better we have to split each one of those two possibilities
Dialogue: 0,0:00:14.68,0:00:20.06,Default,,0000,0000,0000,,into two possibilities each and so we end up with an exponential growth.
Dialogue: 0,0:00:20.06,0:00:24.20,Default,,0000,0000,0000,,And that is why I told you in the beginning that simulating a non-deterministic RAM
Dialogue: 0,0:00:24.20,0:00:29.97,Default,,0000,0000,0000,,on a deterministic RAM is possible, but it's a very unsatisfying simulation
Dialogue: 0,0:00:29.97,0:00:35.63,Default,,0000,0000,0000,,because we pay for it with exponential time and what that means is, for example, for vertex cover,
Dialogue: 0,0:00:35.63,0:00:41.58,Default,,0000,0000,0000,,yes, we can solve vertex cover on a non-deterministic RAM in polynomial time.
Dialogue: 0,0:00:41.58,0:00:45.23,Default,,0000,0000,0000,,But if we do the stimulation of that non-deterministic code,
Dialogue: 0,0:00:45.23,0:00:47.22,Default,,0000,0000,0000,,we end up with exponential time again.
Dialogue: 0,0:00:47.22,0:00:53.11,Default,,0000,0000,0000,,Now of course the question would be, could you simulate a non-deterministic RAM more efficiently?
Dialogue: 0,0:00:53.11,0:00:56.44,Default,,0000,0000,0000,,For example, only using a polynomial number of simulations.
Dialogue: 0,0:00:56.44,0:00:59.10,Default,,0000,0000,0000,,So, in a way we're back where we started.
Dialogue: 0,0:00:59.10,0:01:02.84,Default,,0000,0000,0000,,We found out that we can not simulate a non-deterministic RAM,
Dialogue: 0,0:01:02.84,0:01:05.17,Default,,0000,0000,0000,,but that's going to take us exponential time.
Dialogue: 0,0:01:05.17,0:01:08.52,Default,,0000,0000,0000,,So the question remains, is there a better way to simulate non-determinism
Dialogue: 0,0:01:08.52,0:01:13.41,Default,,0000,0000,0000,,ideally with polynomial time or does simulating non-determinism
Dialogue: 0,0:01:13.41,9:59:59.99,Default,,0000,0000,0000,,on a deterministic RAM always lead to exponential time?