3
$\begingroup$

If strong pseudorandom number generator exists then $BPP=P$ holds and if one way functions exists then $BPP\subseteq SUBEXP$ holds.

  1. What are the best statements we have proved that come close to converse to these statements?

My motivation is this $P=BPP$ and $NP\subseteq P/poly$ are consistent with what we know. However $MCSP\subseteq NP\implies$ $NP\subseteq P/poly$ gives no strong pseudorandom generators in $P/poly$ from Circuit Minimization Problem by Kabanets and Cai.

  1. So is it possible one way functions and pseudorandom number generators are not necessary for derandomization?

It might be that any argument that shows $P=BPP$ implies strong pseudorandom number generator exists should also show $NP\not\subseteq P/poly$ in that case $P=BPP$ and $NP\subseteq P/poly$ should not be consistent with what we know. However I cannot uncover a statement on this.

In an extreme it can very well be that $P=NP$ in which case we have derandomization and no one way functions and pseudorandom number generators. It is not at all clear why these should be considered essential for derandomization.

  1. Are there alternate proofs of $E$ needing exponential circuits for infinite input lengths leading to $P=BPP$ without going through these objects?
$\endgroup$
  • $\begingroup$ "In a World of P=BPP" by Oded Goldreich argues that BPP=P implies existence of some form of PRGs. wisdom.weizmann.ac.il/~oded/PDF/bpp.pdf However, "some form" is technical so I think it is worth reading the details (e.g. the PRGs run in more time, though still polynomial, than the machines it can fool). A more technical summary of the paper might make one good answer to this question ... but I also don't know if it's the last word on that subject. $\endgroup$ – usul Dec 11 '17 at 0:00
  • $\begingroup$ @usul I have made some updates. I am not at all convinced $P=BPP$ implies strong PRGs. $\endgroup$ – Turbo Dec 11 '17 at 0:31
  • $\begingroup$ @usul the key could be 'PRGs in class $P/poly$ under some conditions'. I think $P=BPP$ is consistent with no strong PRGs in $P/poly$ if $E\not\subseteq P/poly$ (which means $P=BPP$ and $MCSP\subseteq NP\subseteq P/poly$ and $E\not\subseteq P/poly$ is possible) but not consistent with no strong PRGs in $P/poly$ if if $E\subseteq P/poly$ (which means $P=BPP$ and $MCSP\subseteq NP\subseteq E\subseteq P/poly$ is not possible). $\endgroup$ – Turbo Dec 11 '17 at 6:08
  • $\begingroup$ Are you aware of Kabanets and Impagliazzo’s paper “Derandomizing Polynomial Identity Tests means proving circuit lower bounds”? $\endgroup$ – Emil Jeřábek Dec 12 '17 at 12:22
  • $\begingroup$ $PIT\in P\implies NEXP\not\subseteq P/poly\mbox{ or }Perm\not\in AlgP/Poly$? $\endgroup$ – Turbo Dec 12 '17 at 12:27

Your Answer

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

Browse other questions tagged or ask your own question.