1
$\begingroup$

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.

|cite|improve this question
$\endgroup$
3
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\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 Jul 18 '17 at 13:36
  • $\begingroup$ And since $P=NP$ then $BPP\subseteq P^P = P$. $\endgroup$ – Covvar Jul 18 '17 at 13:37
  • $\begingroup$ Actually, such $NP$-oracle could exists? $\endgroup$ – Covvar Jul 18 '17 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 Jul 18 '17 at 16:11

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.