1 00:00:00,000 --> 00:00:04,430 And the answer here is that we end up with 2^n simulations, 2 00:00:04,430 --> 00:00:09,660 because each time that we encounter if-better we have to split into two possibilities 3 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 4 00:00:14,680 --> 00:00:20,060 into two possibilities each and so we end up with an exponential growth. 5 00:00:20,060 --> 00:00:24,200 And that is why I told you in the beginning that simulating a non-deterministic RAM 6 00:00:24,200 --> 00:00:29,970 on a deterministic RAM is possible, but it's a very unsatisfying simulation 7 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, 8 00:00:35,630 --> 00:00:41,580 yes, we can solve vertex cover on a non-deterministic RAM in polynomial time. 9 00:00:41,580 --> 00:00:45,230 But if we do the stimulation of that non-deterministic code, 10 00:00:45,230 --> 00:00:47,220 we end up with exponential time again. 11 00:00:47,220 --> 00:00:53,110 Now of course the question would be, could you simulate a non-deterministic RAM more efficiently? 12 00:00:53,110 --> 00:00:56,440 For example, only using a polynomial number of simulations. 13 00:00:56,440 --> 00:00:59,100 So, in a way we're back where we started. 14 00:00:59,100 --> 00:01:02,840 We found out that we can not simulate a non-deterministic RAM, 15 00:01:02,840 --> 00:01:05,170 but that's going to take us exponential time. 16 00:01:05,170 --> 00:01:08,520 So the question remains, is there a better way to simulate non-determinism 17 00:01:08,520 --> 00:01:13,410 ideally with polynomial time or does simulating non-determinism 18 00:01:13,410 --> 99:59:59,999 on a deterministic RAM always lead to exponential time?