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

Beltrán, Carlos; Pardo, Luis

doi:10.1090/S0894-0347-08-00630-9

Smale’s 17th problem: Average polynomial time to compute affine and projective solutions
HTML articles powered by AMS MathViewer

by Carlos Beltrán and Luis Miguel Pardo

J. Amer. Math. Soc. 22 (2009), 363-385

DOI: https://doi.org/10.1090/S0894-0347-08-00630-9

Published electronically: November 6, 2008

PDF | Request permission

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

Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale, Complexity and real computation, Springer-Verlag, New York, 1998. With a foreword by Richard M. Karp. MR 1479636, DOI 10.1007/978-1-4612-0701-6
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, London Math. Soc. Lecture Note Ser., vol. 331, Cambridge Univ. Press, Cambridge, 2006, pp. 1–35. MR 2277103, DOI 10.1017/CBO9780511721571.002
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. MR 2299780, DOI 10.1090/S0025-5718-07-01963-1
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, DOI 10.1007/s10208-005-0176-2
Carlos Beltrán and Luis Miguel Pardo, On Smale’s 17th problem: a probabilistic positive solution, Found. Comput. Math. 8 (2008), no. 1, 1–43. MR 2403529, DOI 10.1007/s10208-005-0211-0

Complexity of Bezout’s Theorem VII: Distance Estimates in the Condition Metric

Online First 10.1007/s10208-007-9018-5

Lenore Blum, Mike Shub, and Steve 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, DOI 10.1090/S0273-0979-1989-15750-9
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, DOI 10.1142/S0218196792000244
F. Cucker, J. L. Montaña, and L. M. Pardo, 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
Stephen A. Cook, A taxonomy of problems with fast parallel algorithms, Inform. and Control 64 (1985), no. 1-3, 2–22. MR 837088, DOI 10.1016/S0019-9958(85)80041-3
Jean-Pierre Dedieu, Estimations for the separation number of a polynomial system, J. Symbolic Comput. 24 (1997), no. 6, 683–693. MR 1487794, DOI 10.1006/jsco.1997.0161
Jean-Pierre Dedieu, 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

Points fixes, zéros et la méthode de newton

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, DOI 10.1002/9781118032916
Neven Elezović, Carla Giordano, and Josip Pec̆arić, The best bounds in Gautschi’s inequality, Math. Inequal. Appl. 3 (2000), no. 2, 239–252. MR 1749300, DOI 10.7153/mia-03-26
Herbert Federer, Geometric measure theory, Die Grundlehren der mathematischen Wissenschaften, Band 153, Springer-Verlag New York, Inc., New York, 1969. MR 0257325
Chung Wu Ho, A note on proper maps, Proc. Amer. Math. Soc. 51 (1975), 237–241. MR 370471, DOI 10.1090/S0002-9939-1975-0370471-3

Analysis on homogeneous spaces

John Hubbard, Dierk Schleicher, and Scott Sutherland, How to find all roots of complex polynomials by Newton’s method, Invent. Math. 146 (2001), no. 1, 1–33. MR 1859017, DOI 10.1007/s002220100149

Sur la méthode de Newton

XXVIII

Myong-Hi Kim, Topological complexity of a root finding algorithm, J. Complexity 5 (1989), no. 3, 331–344. MR 1018023, DOI 10.1016/0885-064X(89)90029-0
Pascal 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, DOI 10.1006/jcom.1996.0019
Gregorio 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, DOI 10.1016/0304-3975(94)00065-4
Gary L. Miller, Riemann’s hypothesis and tests for primality, J. Comput. System Sci. 13 (1976), no. 3, 300–317. MR 480295, DOI 10.1016/S0022-0000(76)80043-8
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, DOI 10.1016/S0020-0190(98)00089-1
Gregorio Malajovich and J. Maurice Rojas, Polynomial systems and the momentum map, Foundations of computational mathematics (Hong Kong, 2000) World Sci. Publ., River Edge, NJ, 2002, pp. 251–266. MR 2021984
Michael O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), no. 1, 128–138. MR 566880, DOI 10.1016/0022-314X(80)90084-0
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, DOI 10.1287/moor.12.1.121
Michael Shub, Some remarks on Bezout’s theorem and complexity theory, From Topology to Computation: Proceedings of the Smalefest (Berkeley, CA, 1990) Springer, New York, 1993, pp. 443–455. MR 1246139

Complexity of Bezout’s Theorem VI: Geodesics in the Condition (number) Metric

Online First 10.1007/s10208-007-9017-6

Steve 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
R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput. 6 (1977), no. 1, 84–85. MR 429721, DOI 10.1137/0206006
R. Solovay and V. Strassen, 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 466001, DOI 10.1137/0207009
Michael Shub and Steve Smale, Complexity of Bézout’s theorem. I. Geometric aspects, J. Amer. Math. Soc. 6 (1993), no. 2, 459–501. MR 1175980, DOI 10.1090/S0894-0347-1993-1175980-4
M. Shub and S. Smale, 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, DOI 10.1007/978-1-4612-2752-6_{1}9
Michael Shub and Steve Smale, 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, DOI 10.1006/jcom.1993.1002
M. Shub and S. Smale, 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, DOI 10.1016/0304-3975(94)90122-8
Michael Shub and Steve Smale, Complexity of Bezout’s theorem. IV. Probability of success; extensions, SIAM J. Numer. Anal. 33 (1996), no. 1, 128–148. MR 1377247, DOI 10.1137/0733008
Jean-Claude 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, DOI 10.1007/BF02141589