Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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 H. Lin Aug 11 '10 at 19:32
    
Real number algorithms as described by Smale with a suitable formulation of P≠NP over R. –  user8232 Aug 11 '10 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 H. Lin Aug 11 '10 at 20:14
    
@Kevin: Thanks for that paper. Question answered. –  user8232 Aug 11 '10 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 '10 at 22:24

1 Answer 1

up vote 6 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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