Welcome to MathOverflow

Question

1

2

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

edited Aug 12 2010 at 22:23

Greg Kuperberg
36.3k●2●116●179

asked Aug 11 2010 at 19:21

unknown (yahoo)
59●5

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. – Kevin Lin Aug 11 2010 at 19:32

Real number algorithms as described by Smale with a suitable formulation of P≠NP over R. – unknown (yahoo) Aug 11 2010 at 19:39

7

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? – Kevin Lin Aug 11 2010 at 20:14

@Kevin: Thanks for that paper. Question answered. – unknown (yahoo) Aug 11 2010 at 20:17

4

@Kevin Let me suggest changing your remark to an answer, so that the question can get closed. – Greg Kuperberg Aug 12 2010 at 22:24

show 1 more comment

Kevin Lin · Accepted Answer · 2010-08-13 08:39:04Z UTC

6

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

answered Aug 13 2010 at 8:39

Kevin Lin
12.9k●2●33●115

Does P≠NP over ℝ imply P≠NP ?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.