Remote Access Journal of the American Mathematical Society
Green Open Access

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?)

  • [BCSS98] L. Blum, F. Cucker, M. Shub, and S. Smale, Complexity and real computation, Springer-Verlag, New York, 1998. MR 1479636 (99a:68070)
  • [BP06] C. Beltrán and L. M. Pardo, On the complexity of non-universal polynomial equation solving: old and new results, Foundations of Computational Mathematics: Santander 2005. L. Pardo, A. Pinkus, E. Süli, M. Todd, editors, Cambridge University Press, 2006, pp. 1-35. MR 2277103 (2008a:65097)
  • [BP07a] C. Beltrán and L. M. Pardo, On the probability distribution of condition numbers of complete intersection varieties and the average radius of convergence of Newton's method in the underdetermined case, Math. Comp. 76 (2007), no. 259, 1393-1424 (electronic). MR 2299780 (2008d:65053)
  • [BP07b] C. Beltrán and L. M. Pardo, Estimates on the distribution of the condition number of singular matrices, Found. Comput. Math. 7 (2007), no. 1, 87-134. MR 2283343 (2008b:65059)
  • [BP08] C. Beltrán and L. M. Pardo, On Smale's 17th problem: a probabilistic positive solution, Found. Comput. Math. 8 (2008), no. 1, 1-43. MR 2403529
  • [BS08] C. Beltrán and M. Shub, Complexity of Bezout's Theorem VII: Distance Estimates in the Condition Metric, J. FoCM Online First 10.1007/s10208-007-9018-5 (2008).
  • [BSS89] L. Blum, M. Shub, and S. Smale, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bull. Amer. Math. Soc. (N.S.) 21 (1989), no. 1, 1-46. MR 974426 (90a:68022)
  • [CMP92] F. Cucker, J. L. Montaña, and L. M. Pardo, Time bounded computations over the reals, Internat. J. Algebra Comput. 2 (1992), no. 4, 395-408. MR 1189670 (93m:03067)
  • [CMP95] -, Models for parallel computation with real numbers, Number-theoretic and algebraic methods in computer science (Moscow, 1993), World Sci. Publ., River Edge, NJ, 1995, pp. 53-63. MR 1377740 (97b:68067)
  • [Coo85] Stephen A. Cook, A taxonomy of problems with fast parallel algorithms, Inform. and Control 64 (1985), no. 1-3, 2-22. MR 837088 (87k:68043)
  • [Ded97] J. P. Dedieu, Estimations for the separation number of a polynomial system, J. Symbolic Comput. 24 (1997), no. 6, 683-693. MR 1487794 (99b:65065)
  • [Ded01] -, Newton's method and some complexity aspects of the zero-finding problem, Foundations of computational mathematics (Oxford, 1999), London Math. Soc. Lecture Note Ser., vol. 284, Cambridge Univ. Press, Cambridge, 2001, pp. 45-67. MR 1836614 (2002d:65050)
  • [Ded06] -, Points fixes, zéros et la méthode de newton, Collection Mathématiques et Applications, Springer, to appear 2006.
  • [DK00] Ding-Zhu Du and Ker-I Ko, Theory of computational complexity, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. MR 1789501 (2001k:68036)
  • [EGP00] N. Elezović, C. Giordano, and J. Pečarić, The best bounds in Gautschi's inequality, Math. Inequal. Appl. 3 (2000), no. 2, 239-252. MR 1749300 (2001g:33001)
  • [Fed69] H. Federer, Geometric measure theory, Die Grundlehren der mathematischen Wissenschaften, Band 153, Springer-Verlag, New York, Inc., New York, 1969. MR 0257325 (41:1976)
  • [Ho75] Chung Wu Ho, A note on proper maps, Proc. Amer. Math. Soc. 51 (1975), 237-241. MR 0370471 (51:6698)
  • [How] R. Howard, Analysis on homogeneous spaces, Class notes, Spring 1994. Royal Institute of Technology, Stocholm.
  • [HSS01] J. Hubbard, D. Schleicher, and S. Sutherland, How to find all roots of complex polynomials by Newton's method, Invent. Math. 146 (2001), no. 1, 1-33. MR 1859017 (2002i:37059)
  • [Kan49] L. Kantorovich, Sur la méthode de Newton, Travaux de l'Institut des Mathématiques Steklov XXVIII (1949), 104-144.
  • [Kim89] M.H. Kim, Topological complexity of a root finding algorithm, J. Complexity 5 (1989), no. 3, 331-344. MR 1018023 (90m:65058)
  • [Koi96] P. Koiran, Hilbert's Nullstellensatz is in the polynomial hierarchy, J. Complexity 12 (1996), no. 4, 273-286, Special issue for the Foundations of Computational Mathematics Conference (Rio de Janeiro, 1997). MR 1422712 (98e:68109)
  • [Mal94] G. Malajovich, On generalized Newton algorithms: quadratic convergence, path-following and error analysis, Theoret. Comput. Sci. 133 (1994), no. 1, 65-84, Selected papers of the Workshop on Continuous Algorithms and Complexity (Barcelona, 1993). MR 1294426 (95g:65073)
  • [Mil76] Gary L. Miller, Riemann's hypothesis and tests for primality, J. Comput. System Sci. 13 (1976), no. 3, 300-317, Working papers presented at the ACM-SIGACT Symposium on the Theory of Computing (Albuquerque, N.M., 1975). MR 0480295 (58:470a)
  • [MP98] J. L. Montaña and Luis M. Pardo, On Kolmogorov complexity in the real Turing machine setting, Inform. Process. Lett. 67 (1998), no. 2, 81-86. MR 1638154 (99c:68134)
  • [MR02] G. Malajovich and J. M. Rojas, Polynomial systems and the momentum map, Foundations of computational mathematics (Hong Kong, 2000), World Sci. Publishing, River Edge, NJ, 2002, pp. 251-266. MR 2021984 (2004k:65090)
  • [Rab80] M. O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), no. 1, 128-138. MR 566880 (81f:10003)
  • [Ren87] J. Renegar, On the efficiency of Newton's method in approximating all zeros of a system of complex polynomials, Math. Oper. Res. 12 (1987), no. 1, 121-148. MR 882846 (88j:65112)
  • [Shu93] M. Shub, Some remarks on Bezout's theorem and complexity theory, From Topology to Computation: Proceedings of the Smalefest (Berkeley, CA, 1990) (New York), Springer, 1993, pp. 443-455. MR 1246139 (95a:14002)
  • [Shu08] -, Complexity of Bezout's Theorem VI: Geodesics in the Condition (number) Metric, J. FoCM Online First 10.1007/s10208-007-9017-6 (2008).
  • [Sma86] S. Smale, Newton's method estimates from data at one point, The merging of disciplines: new directions in pure, applied, and computational mathematics (Laramie, Wyo., 1985), Springer, New York, 1986, pp. 185-196. MR 870648 (88e:65076)
  • [SS77] R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput. 6 (1977), no. 1, 84-85. MR 0429721 (55:2732)
  • [SS78] -, Erratum: ``A fast Monte-Carlo test for primality'' (SIAM J. Comput. 6 (1977), no. 1, 84-85), SIAM J. Comput. 7 (1978), no. 1, 118. MR 0466001 (57:5885)
  • [SS93a] M. Shub and S. Smale, Complexity of Bézout's theorem. I. Geometric aspects, J. Amer. Math. Soc. 6 (1993), no. 2, 459-501. MR 1175980 (93k:65045)
  • [SS93b] -, Complexity of Bezout's theorem. II. Volumes and probabilities, Computational algebraic geometry (Nice, 1992), Progr. Math., vol. 109, Birkhäuser Boston, Boston, MA, 1993, pp. 267-285. MR 1230872 (94m:68086)
  • [SS93c] -, Complexity of Bezout's theorem. III. Condition number and packing, J. Complexity 9 (1993), no. 1, 4-14, Festschrift for Joseph F. Traub, Part I. MR 1213484 (94g:65152)
  • [SS94] -, Complexity of Bezout's theorem. V. Polynomial time, Theoret. Comput. Sci. 133 (1994), no. 1, 141-164, Selected papers of the Workshop on Continuous Algorithms and Complexity (Barcelona, 1993). MR 1294430 (96d:65091)
  • [SS96] -, Complexity of Bezout's theorem. IV. Probability of success; extensions, SIAM J. Numer. Anal. 33 (1996), no. 1, 128-148. MR 1377247 (97k:65310)
  • [Yak95] J. C. Yakoubsohn, A universal constant for the convergence of Newton's method and an application to the classical homotopy method, Numer. Algorithms 9 (1995), no. 3-4, 223-244. MR 1339720 (96d:65092)

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

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

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.

American Mathematical Society