3 ms·

This seems counter intuitive to me. From the article: >BPP is exactly the same as P, but with the difference that the algorithm is allowed to include steps wh

This seems counter intuitive to me. From the article: >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. Also from the article: >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. The reason why I think this seems counter-intuitive: 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. 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 ?

through_17 8y ago
Yes, the article is being a little vague with quantifiers. Let L be a language. L is in BPP if there exist a probabilistic, polynomial time TM such that: For every input x in L, M on x outputs YES with probability close to one. For every input x not in L, M outputs NO with probability close to one. Notice that the input is quantified by "for every" x. The probability in BPP (and thus the error) is only over the random coin tosses that the algorithm uses, not the inputs. This gives our intuition for BPP = P: we can completely eliminate the error using a sufficiently high-quality pseudorandom generator (PRG). We believe that P = BPP because we believe high-quality PRGs exist. More precisely, we can construct such PRGs if there are problems in exponential time that require exponential time even "with advice". Advice is arbitrary information associated with each input length of a problem -- it could even be uncomputable. That is, on all inputs of length n, I get access to a specific string of length poly(n), for instance. That's one string per input length mind, not per input -- if it was per input I could just give you the answer. So such a lower bound is like saying that a certain problem in exponential time is really exponential; there is no strange "compression scheme" that could give us some weird information about all inputs of length n and admit a sub-exponential time solution to the problem. Intuitively, it would be super weird if advice let us cut down on computation time so dramatically. Formally, there are strange consequences if advice is powerful. For instance, if NP is contained in P with polynomial-length advice, PH collapses to the second level (the Karp-Lipton Theorem). On Heuristics: A heuristic is a different notion of complexity: we would instead say for most inputs x, or for any efficiently sample-able distribution over inputs x, the algorithm is correct with high probability. This notion makes perfect sense when combined with deterministic algorithms or with randomized algorithms. In the deterministic setting, the probability is only over the inputs. In the randomized setting, we have a joint probability over inputs and tossed coins.
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 ago
  Your 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.
QML 8y ago
As mentioned below, primality test was something primarily done probabilistically (BPP) until a deterministic algorithm (P) was recently found. The question now is, if we can find a deterministic, polynomial time algorithm for that, why can’t we find the same for all BPP?
- through_17 8y ago
  One reason is that a generic derandomization of BPP would derandomize polynomial identity testing (PIT), an important problem mentioned in the article. Even a very weak derandomization of PIT would imply circuit lower bounds, and these seem quite difficult to prove (see https://eccc.weizmann.ac.il//eccc-reports/2002/TR02-055/index.html https://eccc.weizmann.ac.il//eccc-reports/2002/TR02-055/inde...). It is one thing to derandomize particular algorithms -- often, a single algorithm uses randomness in a limited way. Perhaps the algorithm only uses the fact that truly random bits are pairwise independent -- thus, fully random bits are "overkill" for this algorithm. Swapping out the random bits for pairwise independent bits, which we know how to generate deterministically, suffices. To derandomize all of BPP, we need to understand how any efficient computation could make use of random bits. This seems to require deep insights into the structure of efficient computation -- which we are pretty far from.

through_17 8y ago

Yes, the article is being a little vague with quantifiers. Let L be a language. L is in BPP if there exist a probabilistic, polynomial time TM such that: For every input x in L, M on x outputs YES with probability close to one. For every input x not in L, M outputs NO with probability close to one. Notice that the input is quantified by "for every" x. The probability in BPP (and thus the error) is only over the random coin tosses that the algorithm uses, not the inputs. This gives our intuition for BPP = P: we can completely eliminate the error using a sufficiently high-quality pseudorandom generator (PRG). We believe that P = BPP because we believe high-quality PRGs exist. More precisely, we can construct such PRGs if there are problems in exponential time that require exponential time even "with advice". Advice is arbitrary information associated with each input length of a problem -- it could even be uncomputable. That is, on all inputs of length n, I get access to a specific string of length poly(n), for instance. That's one string per input length mind, not per input -- if it was per input I could just give you the answer. So such a lower bound is like saying that a certain problem in exponential time is really exponential; there is no strange "compression scheme" that could give us some weird information about all inputs of length n and admit a sub-exponential time solution to the problem. Intuitively, it would be super weird if advice let us cut down on computation time so dramatically. Formally, there are strange consequences if advice is powerful. For instance, if NP is contained in P with polynomial-length advice, PH collapses to the second level (the Karp-Lipton Theorem). On Heuristics: A heuristic is a different notion of complexity: we would instead say for most inputs x, or for any efficiently sample-able distribution over inputs x, the algorithm is correct with high probability. This notion makes perfect sense when combined with deterministic algorithms or with randomized algorithms. In the deterministic setting, the probability is only over the inputs. In the randomized setting, we have a joint probability over inputs and tossed coins.

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 ago
Your 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.

QML 8y ago

As mentioned below, primality test was something primarily done probabilistically (BPP) until a deterministic algorithm (P) was recently found. The question now is, if we can find a deterministic, polynomial time algorithm for that, why can’t we find the same for all BPP?

through_17 8y ago
One reason is that a generic derandomization of BPP would derandomize polynomial identity testing (PIT), an important problem mentioned in the article. Even a very weak derandomization of PIT would imply circuit lower bounds, and these seem quite difficult to prove (see https://eccc.weizmann.ac.il//eccc-reports/2002/TR02-055/index.html https://eccc.weizmann.ac.il//eccc-reports/2002/TR02-055/inde...). It is one thing to derandomize particular algorithms -- often, a single algorithm uses randomness in a limited way. Perhaps the algorithm only uses the fact that truly random bits are pairwise independent -- thus, fully random bits are "overkill" for this algorithm. Swapping out the random bits for pairwise independent bits, which we know how to generate deterministically, suffices. To derandomize all of BPP, we need to understand how any efficient computation could make use of random bits. This seems to require deep insights into the structure of efficient computation -- which we are pretty far from.