## ← 22x-08 Nondeterministic Derandomization

• 1 Follower
• 21 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=zz-H9z54FaY" data-team="udacity"></div> 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.