# $P\ne BPP$ implies $P\ne NP$

Prove: $P\ne BPP$ implies $P\ne NP$.

Obviously $P\subseteq BPP$ so the assumption is really $BPP\subsetneq P$. I'm trying to show the implication by contradiction. Let's assume that $P=NP$ and let's look at some language $L\in BPP$. Then, it has a proper probabilistic TM which decides it.

At first, I thought that I could just show some $NP$ machine which uses the $BPP$ machine but a relation between the two classes it not yet known, so it's probably not what I'm supposed to do.

We did learn Adleman's theorem and I think it could be used here (though we haven't define $P/poly$). Adelman's theorem claims that for every $x$ there's a $y$ s.t.

$$x\in A \implies M(x,y) = 1 \\ x\not\in A \implies M(x,y) = 0$$

so it boils down to the problem of finding such $y$, but I don't think this problem (finding $y$) is in $NP$ (or even possible)

Also, I understood that one can use the polynomial hierarchy theorem but we were not taught it.

Use the fact that $\mathsf{BPP}\subseteq\Sigma_2$. Also note that if $P=NP$ then the entire polynomial hierarchy collapses to $P$.

• I think I understand: $\Sigma_2 = NP^{NP}$. We want to show that $BPP\subseteq NP^{NP}$. We define a TM which guesses $y$ (of Adelman's theorem) and the oracle checks if that's the proper $y$. When we reach the desired $y$ we apply $M(x,y)$ and returns accordingly ($M$ is the BPP machine) – Covvar Jul 18 '17 at 13:36
• And since $P=NP$ then $BPP\subseteq P^P = P$. – Covvar Jul 18 '17 at 13:37
• Actually, such $NP$-oracle could exists? – Covvar Jul 18 '17 at 13:39
• I don't see how to directly use Adelman's theorem for this. The standard proof for $\mathsf{BPP}\subseteq\Sigma_2$ goes through linear shifting of subsets of $\{0,1\}^m$, and differentiating small subsets from large ones by their ability to cover all of $\{0,1\}^m$ with a small number of shifts. – Ariel Jul 18 '17 at 16:11