7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What does the subscript $\mathbb{C}$ mean? $\endgroup$ – usul Sep 14 '14 at 15:42
  • 3
    $\begingroup$ @usul: complexityzoo.uwaterloo.ca/Complexity_Zoo:N#npc2 $\endgroup$ – Huck Bennett Sep 14 '14 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$ – Emil Jeřábek Sep 14 '14 at 16:44
  • $\begingroup$ @Anonymous: OK, done. $\endgroup$ – Emil Jeřábek Oct 15 '15 at 11:29
4
$\begingroup$

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

$\endgroup$

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.