## ← 18-16 Strategy Solution

• 1 フォロワー
• 39 Lines

### 埋め込みコードを取得する 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=8JQYBvYE8ps" data-team="udacity"></div> ``` 1言語

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

1. And the correct answers here in my opinion are the first two.
2. The first one is even if the algorithm makes an error with 90% probability, running it only a few times,
3. it does guarantee a correct solution and that of course as you've seen before
4. these probabilities here have to be multiplied with each other if we run the algorithm a couple of times.
5. So, if you run it the first time, of course we have a 90% error chance,
6. but if you run it the second time, we only have (90%)² error chance.
7. If we run it three times, we have (90%)³.
8. And once we have run this algorithm 50 times,
9. we have an error probability of 90%^⁵⁰, which is about 0.5%,
10. and running it a couple of times more of course, we can even get this figure out much much lower.
11. So, since we only have to run it a constant number of times to get the error very very low,
12. it would mean that we're staying still in polynomial time,
13. but we're almost guaranteed a perfect solution.
14. Now, I'm not saying that this is impossible because
15. the laws of NP completeness indeed do not account for randomness
16. but of course it's very very unlikely
17. It's almost the same as with the approximation algorithm
18. where you wouldn't expect an approximation algorithm with
19. an approximation factor of 1.01 even though for some problems
20. it has not been proven that that is impossible but you still wouldn't expect it.
21. Now, the second choice here I think is also correct.
22. And that is basically my reasoning why I say you shouldn't expect this.
23. The number of potential solutions for an NP-complete problem is exponential.
24. Since the algorithm only runs in polynomial time,
25. it can only afford to check a small part of that solution.
26. That is basically the image that we just had
27. where you only able to explore small areas of the whole solution space.
28. And of course you have to employ the strategy.
29. I just think that with this strategy
30. it is highly unlikely to get an algorithm with this performance up here.
31. It just doesn't make sense because you're still poking around a lot.
32. So why would you get a fixed error probability in an exponentially large space
33. if you can only afford to check a polynomial size part of it.
34. And finally as I said the laws of NP completeness indeed
35. do not account for randomness, but the thing is this
36. just because that is so it doesn't mean we should expect anything to happen.
37. Again, I think this is the same thing as with the approximation algorithm.
38. Of course for some problems it would theoretically be possible
39. to have a 1.01 approximation algorithm, but it just seems too unlikely to be true.