patternMinor
Existence of suitable pseudo-random number generators to derandomize BPP to P
Viewed 0 times
randomnumberexistencederandomizebpppseudosuitablegenerators
Problem
I am struggling to understand how the known oracle, and conditional derandomization results connecting $BPP$ and $P$, relate to each other.
My understanding is that if there is a suitably strong pseduo-random number generator that only uses $O(\log n)$ seed bits, then we can derandomize $BPP$ to $P$ by simulating $BPP$ machines in polynomial time using the random number generator and looping over every possible seed. If I understand correctly, the "suitably strong" details were made explicit with Impagliazzo-Wigderson's conditional result that unless $E$ has sub-exponential circuits, $P=BPP$ by way of simulating $BPP$ machines with a pseudo-random number generator.
However, it is known that there is an oracle to which $P^A \ne BPP^A$.
While I understand that this does not imply $P \ne BPP$, cannot we at least say that this means that $P$ cannot simulate $BPP$ machines? Because if $P$ could just simulate $BPP$ machines directly, then it could also access the oracle $A$ in exactly the same way as $BPP$, and it would not be possible to get an oracle separation.
So putting this all together, why can't we say that Impagliazzo-Wigderson's result actually proves $E$ has sub-exponential circuits?
Or alternatively worded, doesn't the oracle separation prove no "suitably strong" pseduo-random number generator exists that would allow derandomizing $BPP$ by just simulating it in polynomial time?
It's possible I'm missing something subtle, but I have a feeling I'm actually just way off the mark. So please help me understand what is going on here.
My understanding is that if there is a suitably strong pseduo-random number generator that only uses $O(\log n)$ seed bits, then we can derandomize $BPP$ to $P$ by simulating $BPP$ machines in polynomial time using the random number generator and looping over every possible seed. If I understand correctly, the "suitably strong" details were made explicit with Impagliazzo-Wigderson's conditional result that unless $E$ has sub-exponential circuits, $P=BPP$ by way of simulating $BPP$ machines with a pseudo-random number generator.
However, it is known that there is an oracle to which $P^A \ne BPP^A$.
While I understand that this does not imply $P \ne BPP$, cannot we at least say that this means that $P$ cannot simulate $BPP$ machines? Because if $P$ could just simulate $BPP$ machines directly, then it could also access the oracle $A$ in exactly the same way as $BPP$, and it would not be possible to get an oracle separation.
So putting this all together, why can't we say that Impagliazzo-Wigderson's result actually proves $E$ has sub-exponential circuits?
Or alternatively worded, doesn't the oracle separation prove no "suitably strong" pseduo-random number generator exists that would allow derandomizing $BPP$ by just simulating it in polynomial time?
It's possible I'm missing something subtle, but I have a feeling I'm actually just way off the mark. So please help me understand what is going on here.
Solution
$P^A\neq BPP^A$ implies the inexistence of strong enough PRG's in the relativized world, not necessarily in the usual (non black box) model.
Remember that when defining a PRG, you require it to fool some adversary with bounded resources, e.g. polynomial size circuits, or probabilistic poly time Turing machines. The NW generator fools circuits of bounded size $S$ (which depends on the hardness of the problem you started your construction with), but this does not mean it can fool circuits (or Turing machines) with access to the oracle $A$.
As an example, for any PRG $G$ which fools poly time probabilistic Turing machines, let $\mathcal{O}_G$ be the oracle which tells you whether some string $s$ is a possible outcome of $G$. $G$ can no longer fool poly size Turing machines with oracle $\mathcal{O}_G$.
Remember that when defining a PRG, you require it to fool some adversary with bounded resources, e.g. polynomial size circuits, or probabilistic poly time Turing machines. The NW generator fools circuits of bounded size $S$ (which depends on the hardness of the problem you started your construction with), but this does not mean it can fool circuits (or Turing machines) with access to the oracle $A$.
As an example, for any PRG $G$ which fools poly time probabilistic Turing machines, let $\mathcal{O}_G$ be the oracle which tells you whether some string $s$ is a possible outcome of $G$. $G$ can no longer fool poly size Turing machines with oracle $\mathcal{O}_G$.
Context
StackExchange Computer Science Q#73873, answer score: 3
Revisions (0)
No revisions yet.