We know that the existence of good pseudorandom generators (PRGs) does not only imply $P=BPP$, but also $PromiseP=PromiseBPP$.

Let us assume $PromiseP\ne PromiseBPP$. Then good PRGs do not exist. However it is still possible that $P=BPP$ holds. If good PRGs do not exist then does $P=BPP$ imply $P=NP$ or is there a possibility $P\neq NP$ still might be true?

Is it possible to have $P=BPP$ without good PRGs and with $P\neq NP$ and with $PromiseP=PromiseBPP$?

  • 6
    $\begingroup$ If $PromiseBPP \neq PromiseP$ then $P \neq NP$. Proof: If $P = NP$ then $PH$ collapses to $P$, so (due to approximate counting in $PH$) we can solve the problem "given a circuit, approximate its acceptance probability" in polynomial time. This in turn implies $PromiseBPP$ is in $PromiseP$ (because this circuit approximation problem is "complete" for $PromiseBPP$). $\endgroup$ – Ryan Williams Oct 26 '18 at 17:54

To put this in complexity terms, could it be possible that P = BPP and EXP has polynomial-size circuits (so no general derandomization)? Relative to a generic oracle you do get P=BPP for all input lengths, and EXP in P/poly for infinitely many lengths, a partial answer to your query. I don't know an oracle where P = BPP and EXP is in P/poly, but I'd think it should be possible.


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.