← 06-13 Simulating A Non-Deterministic Ram

• 1 Follower
• 18 Lines

Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=Gx3xbpLsrWs" data-team="udacity"></div> ``` 1 Language

Showing Revision 1 created 10/03/2012 by Amara Bot.

1. And the answer here is that we end up with 2^n simulations,
2. because each time that we encounter if-better we have to split into two possibilities
3. and then the next time, we encounter if-better we have to split each one of those two possibilities
4. into two possibilities each and so we end up with an exponential growth.
5. And that is why I told you in the beginning that simulating a non-deterministic RAM
6. on a deterministic RAM is possible, but it's a very unsatisfying simulation
7. because we pay for it with exponential time and what that means is, for example, for vertex cover,
8. yes, we can solve vertex cover on a non-deterministic RAM in polynomial time.
9. But if we do the stimulation of that non-deterministic code,
10. we end up with exponential time again.
11. Now of course the question would be, could you simulate a non-deterministic RAM more efficiently?
12. For example, only using a polynomial number of simulations.
13. So, in a way we're back where we started.
14. We found out that we can not simulate a non-deterministic RAM,
15. but that's going to take us exponential time.
16. So the question remains, is there a better way to simulate non-determinism
17. ideally with polynomial time or does simulating non-determinism
18. on a deterministic RAM always lead to exponential time?