# $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
• – Huck Bennett 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.) – Emil Jeřábek Sep 14 '14 at 16:44
• @Anonymous: OK, done. – Emil Jeřábek Oct 15 '15 at 11:29

## 1 Answer

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},$$

which is another way to state Smale’s claim. While it is not directly relevant to the question, note that also

$$\mathrm{NP}\subseteq\mathrm{BPP}\iff\mathrm{NP}=\mathrm{RP}.$$

[1] F. Cucker, M. Karpinski, P. Koiran, T. Lickteig, and K. Werther: On real Turing machines that toss coins. Proceedings of ACM STOC’95, pp. 335–342, 1995. doi:10.1145/225058.225155; preprint