A Short Guide to Hard Problems
quantamagazine.org
quantamagazine.org
I bring this up because, one (heuristic) reason to believe BPP=P is that, in practice, moving PRIMES from BPP to P didn't make a difference.
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 ?
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.
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?"
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) theorem 2.16.
Anyway, if we had good enough lower bounds against procedures with advice (see other comments) we could produce such PRGs.
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?
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.
* Where this work intersects cryptography: in order for cryptosystems to be secure, we generally have to assume the difficulty of certain specific problems: a complexity assumption! Recent work (see here: https://eprint.iacr.org/2015/907) links these assumptions to how easy it is to notice they are false. Intuitively, the easier it is to notice that an assumption is false, the better it is for crypto. A false assumption can be detected and crypto based on this assumption abandoned.
* Where computer search is used to assist proofs: A line of work terminating in https://eccc.weizmann.ac.il//report/2011/031/ used computer search to show time-space tradeoffs for solving satisfiability.
It should be noted that the polynomial hierarchy could conceivably collapse at a higher level even if P!=NP. I wouldn't bet on it though.
Simple constructions using hard decision problems would completely derandomize BPP into P. This is the "hardness to randomness" paradigm: if we could prove that some problem in exponential time was hard enough for circuits, we could completely derandomize BPP. See https://en.wikipedia.org/wiki/Pseudorandom_generator#Pseudor... for more information on this approach.
Unfortunately, the hardness to randomness program is far from realization. Circuit lower bounds are hard to prove; the best known lower bounds separate NONDETERMINISTIC quasi-polynomial (n^(log n)) time from a circuit class with stringent structural restrictions (no threshold gates, constant depth, polynomial size). See https://eccc.weizmann.ac.il/report/2017/188/ for the state of the art, and https://eccc.weizmann.ac.il//eccc-reports/1994/TR94-010/inde... for formal evidence that circuit lower bounds are difficult to prove.
On the other hand, if we are willing to accept "average-case" derandomization, we appear closer to BPP "is basically equal to" P. By "average-case" derandomization, I mean that the deterministic version of the algorithm is wrong on some inputs, but it is impossible to sample those inputs efficiently. This is actually another application of the hardness to randomness paradigm: if we knew EXP != BPP, we would obtain an average-case derandomization of BPP into sub-exponential time. This is not quite what we want, of course: it is an open problem to improve that to fully-polynomial time! See https://link.springer.com/article/10.1007%2Fs00037-007-0233-... for the state of the art in this approach.
Because separations like EXP vs BPP seem easier than circuit lower bounds, (as mentioned in the article, we DO know EXP != P) average-case derandomization seems closer than full derandomization.
For the record, EXP contains BPP, because we can just enumerate over all possible random strings, compute the probability of acceptance, and answer accordingly. I don't think the article mentioned this trivial derandomization. So, that's why getting BPP into even sub-exponential time is an interesting result.