Pergunta

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.

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top