3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

$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$.

$\endgroup$
  • $\begingroup$ This points out where the argument goes wrong, but seems to say something else strong about pseudo-random number generators. For example, the described oracle $O_G$ should not be able to separate between $P$ and $BPP$ because a different generator could just be chosen when simulating $BPP$. To get a separation this way seems like you'd have to have a problem along with an oracle that could distinguish all possible PRG from random with polynomial number of bits. But at that point it feels like there would be a huge rate of false positives with a real RNG. Can this be made explicit? $\endgroup$ – PPenguin Apr 13 '17 at 17:06
  • $\begingroup$ I'm not sure i understand the question. If you want to separate $P$ and $BPP$, then you need to show that derandomization of a certain problem is not possible. It is not trivial to say that such separation can be proven by showing PRGs do not exists. This seems to be the work of this paper wisdom.weizmann.ac.il/~oded/COL/bpp-p.pdf by Goldreich, which constructs "strong enough" PRGs under the assumption of $P=BPP$ (which means that the $P$ vs $BPP$ question can be reduced to the existence of PRGs) $\endgroup$ – Ariel Apr 14 '17 at 9:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.