4 ms·

As mentioned below, primality test was something primarily done probabilistically (BPP) until a deterministic algorithm (P) was recently found. The question no

• 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.