4 ms·
>Can someone explain why it is believed BPP = P ? Someone correct me if I'm wrong, but: One intuition is that if a problem is in BPP, you can repeat the test
by SilasX 8y ago
>Can someone explain why it is believed BPP = P ?
Someone correct me if I'm wrong, but:
One intuition is that if a problem is in BPP, you can repeat the test only a polynomial number of times to get exponentially high confidence in the outcome. That means, in effect, arbitrarily high confidence, very quickly.
So you could have situations where you're more confident in the answer to the question, than in the hardware you're running it on. You would have to believe in some fundamental separation between "arbitrary confidence" and "proof".
There's the joke about "So this randomized algorithm has a low enough error rate that we use it in military encryption or multibillion dollar financial transactions ... but what about theorem proving, where you just can't take any chances?"
- through_17 8y agoYour sketch is correct, but what you're describing is not derandomization. It is "accuracy amplification" by repeating the test. Each round of the test uses more random bits, right? So you're converting more random bits into arbitrary confidence. The objective of derandomization is to completely remove the need to flip random bits from the algorithm. If you had a deterministic PRG, you could completely remove the error from a BPP algorithm. Here is a sketch of why, where I'm eliding the quantitative details: A PRG takes as input a short string of truly random bits (a "seed") and produces as output a long string of "pseudorandom bits". By the definition of a PRG, an efficient algorithm cannot tell the different between the PRG's output and a long string that was really sampled uniformly at random. So, the obvious way to use this to derandomize a BPP machine M is to toss a small number of random bits, run them through the PRG, and use the output of the PRG as the random bits that M would use. We've used the PRG to shrink the amount of randomness required, but not completely eliminate it. To fully eliminate the randomness, brute-force over every possible seed, run M on an input x with each PRG output serving as the random coins, and take the majority vote. This is a fully deterministic process. It is efficient if the ratio between the seed length of the PRG and output length of the PRG is such that 2^(seed length) is still polynomial. The strategy is always correct because, if there is an input y where this brute-force-and-vote strategy fails to produce the correct answer, we can use that input to produce an efficient algorithm that distinguishes between PRG outputs and truly random strings. Why? Because on random bit-strings, M(y,r) usually produces the "right answer" on y, by definition of BPP. On PRG outputs, we just assumed that the majority of answers are wrong, because our vote got the answer wrong! So M(y,random) and M(y,PRG) will tend to disagree. This is a contradiction -- we assumed no efficient procedure could distinguish between PRG outputs and truly random strings. The above is a hasty sketch, that I hope gets a few of the ideas across. See Pseudorandom Generators: A Primer (http://www.wisdom.weizmann.ac.il/~oded/PDF/prg10.pdf http://www.wisdom.weizmann.ac.il/~oded/PDF/prg10.pdf) theorem 2.16. Anyway, if we had good enough lower bounds against procedures with advice (see other comments) we could produce such PRGs.