If P != NP, then BPP in P
We really really want to prove:
which will give \text{P} = \text{BPP}.
How about we replace the truly random bits on the random tape r \in \left\{0,1\right\}^{\text{poly}\left(|x|\right)} with “pseudo-randomness” bits and prove that M can’t tell the difference.
Namely, a thing that is “pseudo-random” is easier to brute force over. So, we ideally can brute force over \text{poly}\left(n\right) many outcomes instead of 2^{\text{poly}\left(n\right)} in the case of true randomness.
We see that if we believe P \neq NP, then we can execute this plan above. In particular, since M is just a normal Turing Machine \in P, if P \neq NP, then we think there’s surely there’s a way to fool M by taking up the gap.
Assume a pseudorandom generator (which takes a small input, because that’s nicely brute forcable):
Naively doing this is certainty doesn’t result in a uniform output distribution; because G is wildly not surjective — there are 2^{\log n} = n possible input values, and 2^{n} possible outputs.
We want M to not be able to tell the difference, in particular meaning we want G to be scrambly enough o that M can’t tell the diffidence between these two pictures.
We can’t technically do this but we need to construct G mapping G: \left\{0,1\right\}^{\log n} \to \left\{0,1\right\}^{n} with…
G is computer poly \left(n\right) (in particular n^{3} time—i.e. more time than the underlying turing machine) for all randomized n^{2} time, turing machine, \forall x \in \left\{01\right\}^{*}, we desire: \begin{equation} Pr_{r \sim \left{0,1\right}^{n}}, \left[M \left(x,r\right), \text{accept}\right] = Pr\left[M\left(x, G\left(s\right)\right))\right] \pm 0.1 \end{equation}
i.e. it’s “fooled” by G
insight: randomness derives from the inability for M to compute harder than n^{2}. “Randomness is in the eye of the beholder.”