4
$\begingroup$

What are implications of $\mathsf{P}\neq\mathsf{NP}$ in $\mathsf{BSS}$ model to $\mathsf{Turing}$ model and $\mathsf{Valiant's}$ counting complexity model?

In opposite direction what are implications of $\mathsf{P}=\mathsf{NP}$ in $\mathsf{BSS}$ model to $\mathsf{Turing}$ model and $\mathsf{Valiant's}$ counting complexity model?

Improve this question
$\endgroup$
  • $\begingroup$ I think this has been asked before. Have tried searching for it? $\endgroup$ – Kaveh Aug 30 '15 at 0:05
  • 1
    $\begingroup$ I got $VNP$ versus $VP$ implication in search not this. $\endgroup$ – user34945 Aug 30 '15 at 0:06
  • $\begingroup$ AFAIK, the Boolean part of $P_{\mathbb{R}}$ lies in the counting hierarchy (by reduction to PosSLP) and $NP_{\mathbb{R}}$ is contained in PSPACE (See "On the complexity of numerical analysis" by Allender, Burgisser, Pedersen and Miltersen). So this should imply a separation between P and PSPACE? $\endgroup$ – Nikhil Aug 30 '15 at 12:01
3
$\begingroup$

$\newcommand\Ptime{\mathsf P} \newcommand\NP{\mathsf{NP}} \newcommand\poly{\mathsf{poly}}$ It is known that $\Ptime/\poly \neq \NP/\poly \implies \Ptime_{\mathbb C}\neq \NP_\mathbb{C}$ [1] where the latter two represent the classes $\Ptime$ and $\NP$ in the BSS model over the complex numbers. (You can take the contrapositive to obtain a consequence of $\Ptime_\mathbb C = \NP_\mathbb C$.) To the best of my knowledge, this is the only known result, though results of the same kind are known for other classes (in particular in Koiran's weak model).

For more on this, look at Chapter 1 (in particular Fig. 1.1) and Chapter 8 of Bürgisser's book [2].

[1] F. Cucker, M. Karpinski, P. Koiran, T. Lickteig, and K. Werther. On real Turing machines that toss coins. In Proc. 27th ACM STOC, Las Vegas, pages 335–342, 1995.
[2] Peter Bürgisser. Completeness and reductions in algebraic complexity theory, 1998.

Improve this answer
$\endgroup$
  • $\begingroup$ where in $[1]$ does it say $\mathsf{P/Poly}\neq\mathsf{NP/poly}\implies \mathsf{P_{\Bbb C}}\neq\mathsf{NP_{\Bbb C}}$? $\endgroup$ – 1.. Jul 11 '16 at 4:16
  • $\begingroup$ also does failure of $\tau$ conjecture imply $\mathsf{P_{\Bbb C}}\neq\mathsf{NP_{\Bbb C}}$? or does $\mathsf{P_{\Bbb C}}\neq\mathsf{NP_{\Bbb C}}\iff \mathsf{P_{\Bbb R}}\neq\mathsf{NP_{\Bbb R}}$ hold? $\endgroup$ – 1.. Jul 11 '16 at 4:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy