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.


1 Answer 1


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

  • $\begingroup$ 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) $\endgroup$
    – Covvar
    Commented Jul 18, 2017 at 13:36
  • $\begingroup$ And since $P=NP$ then $BPP\subseteq P^P = P$. $\endgroup$
    – Covvar
    Commented Jul 18, 2017 at 13:37
  • $\begingroup$ Actually, such $NP$-oracle could exists? $\endgroup$
    – Covvar
    Commented Jul 18, 2017 at 13:39
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ariel
    Commented Jul 18, 2017 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.