2
$\begingroup$

Does P≠NP over ℝ imply P≠NP ?

where ℝ is for Real number algorithms as described by Smale with a suitable formulation of P≠NP over ℝ.

Complexity Theory and Numerical Analysis, Steve Smale, 2000 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.4678&rep=rep1&type=pdf

$\endgroup$
6
  • $\begingroup$ Please give more information. Presumably you're talking about the Blum-Shub-Smale model of computation, and presumably by "R" you mean the real numbers. $\endgroup$ Aug 11, 2010 at 19:32
  • $\begingroup$ Real number algorithms as described by Smale with a suitable formulation of P≠NP over R. $\endgroup$
    – user8232
    Aug 11, 2010 at 19:39
  • 7
    $\begingroup$ Some years ago I read the paper "Computing over the Reals, Where Turing Meets Newton" by Lenore Blum, in which this question and related questions ("transfer results") are addressed. Have you read this paper? $\endgroup$ Aug 11, 2010 at 20:14
  • $\begingroup$ @Kevin: Thanks for that paper. Question answered. $\endgroup$
    – user8232
    Aug 11, 2010 at 20:17
  • 4
    $\begingroup$ @Kevin Let me suggest changing your remark to an answer, so that the question can get closed. $\endgroup$ Aug 12, 2010 at 22:24

1 Answer 1

7
$\begingroup$

Some years ago I read the paper "Computing over the Reals, Where Turing Meets Newton" by Lenore Blum, in which this question and related questions ("transfer results") are addressed: http://www.ams.org/notices/200409/fea-blum.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.