<p>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</p>

<p>$$\mathrm{NP}_\mathbb C=\mathrm P_\mathbb C\implies\mathrm{NP}\subseteq\mathrm{BPP},$$</p>

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

<p>$$\mathrm{NP}\subseteq\mathrm{BPP}\iff\mathrm{NP}=\mathrm{RP}.$$</p>

<p>[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. <a href="http://dx.doi.org/10.1145/225058.225155" rel="noreferrer">doi:10.1145/225058.225155</a>; <a href="http://theory.cs.uni-bonn.de/~marek/publications/coins.ps.gz" rel="noreferrer">preprint</a></p>

CC BY-SA 3.0
2015-10-15T11:28:47.027Z
2015-10-15T11:28:47.027Z
Emil Jeřábek
<p><a href="https://en.wikipedia.org/wiki/Stephen_Smale" rel="nofollow">Stephen Smale</a> claims in <a href="http://dx.doi.org/10.1007/BF03025291" rel="nofollow">Mathematical Problems for the Next Century</a> that </p>

<p>$$NP \not\subseteq BPP \implies NP_{\mathbb{C}} \not\subseteq P_{\mathbb{C}}.$$</p>

<p>Can someone sketch the argument or provide a reference?</p>

<p>Is there any similar result in the reverse direction?</p>

<p><a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#npc2" rel="nofollow">$NP_{\mathbb{C}}$</a> (<a href="http://books.google.com/books?id=zxtrVqUP-AwC&amp;pg=PA100" rel="nofollow">definition</a>) and <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:P#pc" rel="nofollow">$P_{\mathbb{C}}$</a> (<a href="http://books.google.com/books?id=zxtrVqUP-AwC&amp;pg=PA86" rel="nofollow">definition</a>) are NP and P over complex numbers $\mathbb{C}$ using <a href="https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine" rel="nofollow">the Blum–Shub–Smale machine model</a>. </p>

CC BY-SA 3.0
2014-09-14T15:42:59.680Z
What does the subscript $\mathbb{C}$ mean?
usul
CC BY-SA 3.0
2014-09-14T16:32:42.590Z
@usul: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#npc2
Huck Bennett
CC BY-SA 3.0
2014-09-14T16:44:14.623Z
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
CC BY-SA 3.0
2015-10-15T11:29:15.343Z
@Anonymous: OK, done.
Emil Jeřábek
<cc.complexity-theory><algebraic-complexity>
$NP \not\subseteq BPP \implies NP_{\mathbb{C}} \not\subseteq P_{\mathbb{C}}$
Anonymous
# $NP \not\subseteq BPP \implies NP_{\mathbb{C}} \not\subseteq P_{\mathbb{C}}$

(Asked by: username_0 on 2014-09-14)

[Stephen Smale](https://en.wikipedia.org/wiki/Stephen_Smale) claims in [Mathematical Problems for the Next Century](http://dx.doi.org/10.1007/BF03025291) 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}}$](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#npc2) ([definition](http://books.google.com/books?id=zxtrVqUP-AwC&pg=PA100)) and [$P\_{\mathbb{C}}$](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:P#pc) ([definition](http://books.google.com/books?id=zxtrVqUP-AwC&pg=PA86)) are NP and P over complex numbers $\mathbb{C}$ using [the Blum–Shub–Smale machine model](https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine).

**Tags:** cc.complexity-theory, algebraic-complexity

> **Comments:**
> **username_1**: What does the subscript $\mathbb{C}$ mean?  
> **username_2**: @username_1: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#npc2  
> **username_3**: 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.)  
> **username_3**: @username_0: OK, done.  

---

## 1 answers

### Answer by username_3 on 2015-10-15. Score: 5 | Accepted 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](http://dx.doi.org/10.1145/225058.225155); [preprint](http://theory.cs.uni-bonn.de/~marek/publications/coins.ps.gz)


---

