# $NP \not\subseteq BPP \implies NP_{\mathbb{C}} \not\subseteq P_{\mathbb{C}}$

$$NP \not\subseteq BPP \implies NP_{\mathbb{C}} \not\subseteq P_{\mathbb{C}}.$$

Can someone sketch the argument or provide a reference?

Is there any similar result in the reverse direction?

$NP_{\mathbb{C}}$ (definition) and $P_{\mathbb{C}}$ (definition) are NP and P over complex numbers $\mathbb{C}$ using the Blum–Shub–Smale machine model.

• What does the subscript $\mathbb{C}$ mean?
– usul
Sep 14 '14 at 15:42
• Sep 14 '14 at 16:32
• The [CKK+95] reference in the zoo entry also seems to answer the question: Boolean languages computable in $P_\mathbb C$ are in BPP. (They actually state it for $P_\mathbb R$ without inequality tests, but that’s equivalent.) Sep 14 '14 at 16:44
• @Anonymous: OK, done. Oct 15 '15 at 11:29

As proved in [1], Boolean languages computable in $\mathrm P_\mathbb C$ are in $\mathrm{BPP}$. (They state it for $\mathrm P_\mathbb R$ without inequality tests, which amounts to the same thing.) On the other hand, Boolean NP-languages are computable in $\mathrm{NP}_\mathbb C$, hence
$$\mathrm{NP}_\mathbb C=\mathrm P_\mathbb C\implies\mathrm{NP}\subseteq\mathrm{BPP},$$
$$\mathrm{NP}\subseteq\mathrm{BPP}\iff\mathrm{NP}=\mathrm{RP}.$$