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$
3
  • $\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, 2015 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, 2015 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, 2015 at 8:37

1 Answer 1

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$
4
  • 1
    $\begingroup$ The words 'such as' seems to suggest there are possibly more important implications. $\endgroup$
    – Turbo
    Aug 23, 2015 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$ Aug 24, 2015 at 5:41
  • $\begingroup$ would there be any barriers to a possible proof? $\endgroup$
    – Turbo
    Aug 25, 2015 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$ Aug 25, 2015 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.