Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Journal of the American Mathematical Society
Journal of the American Mathematical Society
ISSN 1088-6834(online) ISSN 0894-0347(print)

 

Smale's 17th problem: Average polynomial time to compute affine and projective solutions


Authors: Carlos Beltrán and Luis Miguel Pardo
Journal: J. Amer. Math. Soc. 22 (2009), 363-385
MSC (2000): Primary 65H20, 14Q20; Secondary 12Y05, 90C30
Published electronically: November 6, 2008
MathSciNet review: 2476778
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Smale's 17th problem asks: ``Can a zero of $ n$ complex polynomial equations in $ n$ unknowns be found approximately, on the average, in polynomial time with a uniform algorithm?'' We give a positive answer to this question. Namely, we describe a uniform probabilistic algorithm that computes an approximate zero of systems of polynomial equations $ f:\mathbb{C}^n\longrightarrow\mathbb{C}^n$, performing a number of arithmetic operations which is polynomial in the size of the input, on the average.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2000): 65H20, 14Q20, 12Y05, 90C30

Retrieve articles in all journals with MSC (2000): 65H20, 14Q20, 12Y05, 90C30


Additional Information

Carlos Beltrán
Affiliation: Departmento de Matemáticas, Estadística y Computación. Fac. de Ciencias. Avda. Los Castros s/n. 39005 Santander, Spain
Email: beltranc@unican.es

Luis Miguel Pardo
Affiliation: Departmento de Matemáticas, Estadística y Computación. Fac. de Ciencias. Avda. Los Castros s/n. 39005 Santander, Spain
Email: luis.pardo@unican.es

DOI: http://dx.doi.org/10.1090/S0894-0347-08-00630-9
PII: S 0894-0347(08)00630-9
Keywords: Approximate zero, homotopy methods, complexity of methods in algebraic geometry
Received by editor(s): November 2, 2006
Published electronically: November 6, 2008
Additional Notes: The authors’ research was partially supported by FECYT, Spanish Ministry of Science, MTM2007-62799, and an NSERC grant.
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.