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}$?
$\begingroup$
$\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$– user12859Commented 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$– TurboCommented 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$– user12859Commented Aug 22, 2015 at 8:37
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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!
-
1$\begingroup$ The words 'such as' seems to suggest there are possibly more important implications. $\endgroup$– TurboCommented 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$ Commented Aug 24, 2015 at 5:41
-
$\begingroup$ would there be any barriers to a possible proof? $\endgroup$– TurboCommented 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$ Commented Aug 25, 2015 at 4:35