Why would the existence of a sufficiently strong PRNG prove P=BPP?

Question

The $P$ vs $BPP$ question is often explained as such: if there exists a "strong enough" PRNG, we can use it to derandomize any randomized algorithm.

However, I don't get how this, let's call it "$PRNG = RNG$" idea implies $P = BPP$ at all. In fact, $P = BPP$ seems like it would be much, much harder to prove!

The main problem is that algorithms in $BPP$ are only required to be correct, let's say, 51% of the time. So, if we use some deterministic PRNG, we would thus expect it to be correct on 51% of instances. We can run the algorithm multiple times and take the majority result to get this number up to 75%, or 99% or whatever we want. But doing so won't bring it to exactly 100%.

Put another way, this would really entail that "$BPP \subset P_{\text{only correct for 51%/75%/99%/etc of instances}}$." But to qualify for $P$, it needs to give the correct answer every single time, for all instances, with no possible chance of failure at all. That is a much, much higher bar!

In general, while I don't have any problems believing "$BPP \subset P_{\text{only correct for 51%/75%/99%/etc of instances}}$", I don't get how you are supposed to go the last mile and actually get it all the way to 100%.

---

The idea is apparently this: we can run the algorithm on every possible random bitstring it could possibly use and take the majority result. This takes exponential time. But it is conjectured that we can get the same correct result every single time by using a special PRNG and just brute forcing all the random seeds instead.

But again: we need a 100% success rate! If we think of the set of "all possible PRNG outputs" as a "sample" of "all possible bitstrings," we need to somehow magically guarantee it is never an "outlier" for any instance, ever. How can we do that?

Answer 1

Let $A$ be a BPP algorithm for the problem, i.e., $A$ runs in polynomial time, uses randomness, and is correct with probability at least 2/3 on every input.

Now let's assume we have a PRNG that requires exponential time to distinguish its output from random. In other words, if the seed length is $s$, it takes at least $2^s$ steps to distinguish its output from random. (This is a strong assumption, stronger than standard cryptographic assumptions: e.g., it needs to resist super-polynomial sub-exponential time distinguishers.) (Recall that the definition of what it means for a PRNG to be cryptographically strong is that there does not exist any efficient distinguisher, i.e., any efficient algorithm that can distinguish its output from random bits. See https://crypto.stackexchange.com/q/12436/351, https://crypto.stackexchange.com/q/39186/351, https://crypto.stackexchange.com/q/32267/351, https://crypto.stackexchange.com/q/51882/351, https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator#Definitions, https://en.wikipedia.org/wiki/Computational_indistinguishability.)

Suppose the running time of $A$ is $O(n^5)$. Let's instantiate the PRNG with seed length $s=10 \lg n$. Let $\hat{A}$ denote running $A$, but using the output of the PRNG (on a seed generated uniformly at random) instead of truly random bits.

By our assumption on the security of the PRNG, distinguishing the PRNG's output from random needs at least $2^s=n^{10}$ steps. Since the running time of $A$ is much less than that, $A$ cannot distinguish the PRNG's output from random. Consequently, the output of $A$ when run on the PRNG's output is very similar to its output when run on truly random bits. In particular, $\hat{A}$ is correct with probability at least $7/12$ (say) on every input. (Why? If not, you could use $\hat{A}$ to distinguish the PRNG's output from random.)

This means that, for every input $x$, out of all $2^s$ possible seeds for the PRNG, at least $(7/12) \cdot 2^s$ of them cause $\hat{A}$ to give the correct answer. In particular, a strict majority of the seeds cause $\hat{A}$ to output the correct answer (and this is true for all input $x$).

Therefore, we'll construct a new algorithm $B$, which works as follows: enumerate all $2^s=2^{10\lg n}=n^{10}$ possible seeds, for each run $\hat{A}(x)$ on that seed, and take a majority vote of the answers. By the above remarks, the majority is guaranteed to be the correct answer (always, for all $x$).

We find that $B$ is a deterministic algorithm that always produces the correct answer. Also, the running time of $B$ is $O(n^{15})$, since we run $A$ $n^{10}$ times, and each time takes $O(n^5)$ time. It follows that $B$ runs in polynomial time, so $B$ is a P algorithm.

We have proven that if there is any BPP algorithm for some problem, then there is a P algorithm for that problem, assuming there are PRNGs that require exponential time to break.