|
The article lists what we'd like to know, but the research frontiers for each class are also interesting. In each case, how far are we from our objectives? I'll sketch a little bit of the situation for BPP below. 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. |