Stephen Smale claims in Mathematical Problems for the Next Century that

$$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.

  • 1
    $\begingroup$ What does the subscript $\mathbb{C}$ mean? $\endgroup$
    – usul
    Sep 14, 2014 at 15:42
  • 3
    $\begingroup$ @usul: complexityzoo.uwaterloo.ca/Complexity_Zoo:N#npc2 $\endgroup$ Sep 14, 2014 at 16:32
  • 5
    $\begingroup$ 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.) $\endgroup$ Sep 14, 2014 at 16:44
  • $\begingroup$ @Anonymous: OK, done. $\endgroup$ Oct 15, 2015 at 11:29

1 Answer 1


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


[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


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.