YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← 22x-08 Nondeterministic Derandomization

Get Embed Code
1 Language

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

  1. Say we have a decision problem, and let's call it Problem-X.
  2. Now since it's a decision problem,
  3. the solution to this problem is just either a yes or no answer.
  4. Now let's also say that we have figured out
  5. a randomized algorithm for this problem,
  6. and we know that the randomized algorithm
  7. returns the correct decision, yes or no, with a probability of 75 percent.
  8. Now let's say that the randomized algorithm runs in polynomial time
  9. and that the type of randomization it uses is basically just a coin flip.
  10. So at certain points in the code it just flips a coin,
  11. and decides to continue execution at one of two places at random.
  12. I'd like to know which of the following statements are true.
  13. That the algorithm can be used to produce a correct answer
  14. with 99 percent probability in polynomial time.
  15. That the algorithm can be modified to always produce a correct solution
  16. on a nondeterministic RAM in polynomial time.
  17. Rather that it can be modified in the same way
  18. to produce a correct solution on a deterministic RAM in exponential time.
  19. And finally I'd like to know if Problem-X is in NP
  20. and also if it's NP-complete.
  21. So check all that are true statements.