A Short Guide to Hard Problems
This seems counter intuitive to me.<p>From the article:<p>>BPP is exactly the same as P, but with the difference that the algorithm is allowed to include steps where its decision-making is randomized. Algorithms in BPP are required only to give the right answer with a probability close to 1.<p>Also from the article:<p>>Computer scientists would like to know whether BPP = P. If that is true, it would mean that every randomized algorithm can be de-randomized. They believe this is the case — that there is an efficient deterministic algorithm for every problem for which there exists an efficient randomized algorithm — but they have not been able to prove it.<p>The reason why I think this seems counter-intuitive:<p>The BPP is only required to give the right answer most of the time (with a probability close to 1). So... A heuristic solution. It seems counter-intuitive that a not-always-correct solution can have a deterministic solution in P. You could get higher and higher probability of the solution repeating N times... So N*O(original). But it seems like that slice of probability that is given up in the heuristic shortcut could be significant... Adding an N multiplier to O(N^2) would still be polynomial but you also still wouldn't be deterministic, just approach deterministic.<p>Maybe I am mixing heuristics and probability where they shouldn't be, or maybe there's a good reason to think the heuristic can always be reformulated to deterministic? Because you can approach the answer with increasing certainty and stay in P? Can someone explain why it is believed BPP = P ?