2
$\begingroup$

If $\mathsf{NP\subseteq BPP}$, then we know that $\mathsf{NP\subseteq RP}$ (http://www.csie.ntu.edu.tw/~lyuu/complexity/2011/20120103s.pdf). Does $\mathsf{NP\subseteq BPP}$ also imply $\mathsf{NP\subseteq coRP}$ and hence $\mathsf{NP\subseteq BPP}$ also imply $\mathsf{NP\subseteq ZPP}$?

$\endgroup$
  • $\begingroup$ I believe that's not even known to imply $\: UP\subseteq ZPP \;$. $\;\;\;$ (On the other hand, I also don't know of any oracle relative to which the implication fails.) $\;\;\;\;\;\;\;\;$ $\endgroup$ – user12859 Aug 22 '15 at 6:31
  • $\begingroup$ @RickyDemer $\mathsf{NP\subseteq BPP\implies NP\subseteq coBPP}$ since $\mathsf{BPP=coBPP}$. Could we switch the arguments in attached proof to yield $\mathsf{NP\subseteq coRP}$? $\endgroup$ – Turbo Aug 22 '15 at 8:23
  • $\begingroup$ No, since it's far from clear that there's any way to efficiently become certain $\hspace{1.76 in}$ of non-membership in an NP language. $\;$ $\endgroup$ – user12859 Aug 22 '15 at 8:37
5
$\begingroup$

If you could prove that implication, then lower bounds such as $NEXP \neq BPP$ would hold unconditionally. (proof: $NEXP = BPP$ implies $NEXP = \Sigma_2 P$ and $NP \subset BPP$, and if the latter also implies $NP$ is in $coRP$ then UNSAT is in $NP$. So $NEXP = \Sigma_2 P = NP$ which is false by the nondeterministic time hierarchy). Good luck!

$\endgroup$
  • 1
    $\begingroup$ The words 'such as' seems to suggest there are possibly more important implications. $\endgroup$ – Turbo Aug 23 '15 at 5:01
  • $\begingroup$ Well, implicitly in the above argument we would also have NP in BPP implying NP = coNP. So this would be like some "super Karp Lipton" theorem you could stick into other existing arguments. For example if NP is in BPP then NP also doesn't have fixed polynomial size circuits. And so on. $\endgroup$ – Ryan Williams Aug 24 '15 at 5:41
  • $\begingroup$ would there be any barriers to a possible proof? $\endgroup$ – Turbo Aug 25 '15 at 1:16
  • 2
    $\begingroup$ There are oracles relative to which the implication can't hold (e.g. Oracles making NEXP equal to BPP) $\endgroup$ – Ryan Williams Aug 25 '15 at 4:35

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.