Skip to main content
3 of 3
Correct the answer
D.W.
  • 165.6k
  • 21
  • 230
  • 490

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.

D.W.
  • 165.6k
  • 21
  • 230
  • 490