English subtitles

← 06-11 Building A Non-Deterministic Ram

Get Embed Code
1 Language

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

  1. And there are two correct answers here.
  2. The first one is the simulation takes longer by a polynomial time factor.
  3. Now, it's a bit difficult if you wanted to specify exactly
  4. how much longer a simulation like this takes.
  5. In my point of view, you would not even take polynomially longer but only a constant factor,
  6. but polynomial is safe enough because in this course we're mostly
  7. differentiating between polynomial and exponential running time.
  8. Now, the reason why it only takes polynomial time longer is that, as I said before,
  9. once we're in the certain line of code, this line of code specifies exactly what is going to happen next.
  10. So it's mostly an overhead of simulating what this line here of code does, but as we said
  11. when we specify the RAM model, each line here is a simple operations, so it takes constant
  12. amount of time on the RAM.
  13. I think it's fair to say that it will only take polynomially more time if you simulate what it does.
  14. It doesn't do anything really complex. So the second answer here is wrong.
  15. The simulation is also always correct because there's no involvement of randomness
  16. or guessing and such.
  17. So if the simulator is programmed correctly, we will always get
  18. the same result that we would have originally gotten.
  19. It only takes longer time.