English 字幕

← 18-16 Strategy Solution



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.