It is believed showing $BPP$ in $P$ involves good $PRG$s and faces lower bound barriers.

  1. Does showing $BPP$ in $P^{NP}$ which would mean $BPP\neq EXP^{NP}$ face similar $PRG$ and give lower bounds?

  2. Does $BPP$ in $P^{NP}$ and $SAT$ is in $2^{n}/f(n)$ at a superpolynomial $f(n)$ give anything for $BPP$ other than $BPP\neq NEXP$ ($NEXP\not\subseteq P/poly$ would hold)?

  3. $BPP\neq EXP^{NP}$ and $BPP\neq NEXP$ mean $BPP\neq EXP^{NP}\cup NEXP$. What does this mean for lower bounds?

  4. How far would we be away from $BPP\neq EXP$? Does this truly need good $PRG$s if $BPP\neq EXP^{NP}\cup NEXP$ is achieved without constructing good $PRG$s?

  • 3
    $\begingroup$ I think that by "derandomizing to P^NP" the OP means showing that BPP is in P^NP. $\endgroup$ – Huck Bennett Feb 19 '19 at 21:29

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.