WEBVTT
00:00:00.000 --> 00:00:04.430
And the answer here is that we end up with 2^n simulations,
00:00:04.430 --> 00:00:09.660
because each time that we encounter if-better we have to split into two possibilities
00:00:09.660 --> 00:00:14.680
and then the next time, we encounter if-better we have to split each one of those two possibilities
00:00:14.680 --> 00:00:20.060
into two possibilities each and so we end up with an exponential growth.
00:00:20.060 --> 00:00:24.200
And that is why I told you in the beginning that simulating a non-deterministic RAM
00:00:24.200 --> 00:00:29.970
on a deterministic RAM is possible, but it's a very unsatisfying simulation
00:00:29.970 --> 00:00:35.630
because we pay for it with exponential time and what that means is, for example, for vertex cover,
00:00:35.630 --> 00:00:41.580
yes, we can solve vertex cover on a non-deterministic RAM in polynomial time.
00:00:41.580 --> 00:00:45.230
But if we do the stimulation of that non-deterministic code,
00:00:45.230 --> 00:00:47.220
we end up with exponential time again.
00:00:47.220 --> 00:00:53.110
Now of course the question would be, could you simulate a non-deterministic RAM more efficiently?
00:00:53.110 --> 00:00:56.440
For example, only using a polynomial number of simulations.
00:00:56.440 --> 00:00:59.100
So, in a way we're back where we started.
00:00:59.100 --> 00:01:02.840
We found out that we can not simulate a non-deterministic RAM,
00:01:02.840 --> 00:01:05.170
but that's going to take us exponential time.
00:01:05.170 --> 00:01:08.520
So the question remains, is there a better way to simulate non-determinism
00:01:08.520 --> 00:01:13.410
ideally with polynomial time or does simulating non-determinism
00:01:13.410 --> 99:59:59.999
on a deterministic RAM always lead to exponential time?