<p>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. </p>

CC BY-SA 4.0
2018-11-06T21:47:19.497Z
2018-11-06T21:47:19.497Z
Lance Fortnow
<p><s>We know that the existence of good pseudorandom generators (PRGs) does not only imply <span class="math-container">$P=BPP$</span>, but also <span class="math-container">$PromiseP=PromiseBPP$</span>. </p>

<p>Let us assume <span class="math-container">$PromiseP\ne PromiseBPP$</span>. Then good PRGs do not exist. However it is still possible that <span class="math-container">$P=BPP$</span> holds. If good PRGs do not exist then does <span class="math-container">$P=BPP$</span> imply <span class="math-container">$P=NP$</span> or is there a possibility <span class="math-container">$P\neq NP$</span> still might be true?</s></p>

<p>Is it possible to have <span class="math-container">$P=BPP$</span> without good PRGs and with <span class="math-container">$P\neq NP$</span> and with <span class="math-container">$PromiseP=PromiseBPP$</span>?</p>

CC BY-SA 4.0
2018-10-26T17:54:42.757Z
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$).
Ryan Williams
<cc.complexity-theory><complexity-classes>
$P=BPP$ without good PRGs?
Turbo
# $P=BPP$ without good PRGs?

(Asked by: username_0 on 2018-10-26)

~~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$?

**Tags:** cc.complexity-theory, complexity-classes
> **Comments:**
> **username_1**: 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$).  

---

## 1 answers

### Answer by username_2 on 2018-11-06. Score: 3

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.


---

