English subtitles

← 06-13 Simulating A Non-Deterministic Ram

Get Embed Code
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?