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

Beltrán, Carlos¹ ; Pardo, Luis¹

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

Journal of the American Mathematical Society, Tome 22 (2009) no. 2, pp. 363-385

Résumé

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.

Détail

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

Bibliographie

[1] Blum, Lenore, Cucker, Felipe, Shub, Michael, Smale, Steve Complexity and real computation 1998

[2] Beltrã¡N, C., Pardo, L. M. On the complexity of non universal polynomial equation solving: old and new results 2006 1 35

[3] Beltrã¡N, C., Pardo, L. M. 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. 2007 1393 1424

[4] Beltrã¡N, C., Pardo, L. M. Estimates on the distribution of the condition number of singular matrices Found. Comput. Math. 2007 87 134

[5] Beltrã¡N, Carlos, Pardo, Luis Miguel On Smale’s 17th problem: a probabilistic positive solution Found. Comput. Math. 2008 1 43

[6] Blum, Lenore, Shub, Mike, Smale, Steve On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines Bull. Amer. Math. Soc. (N.S.) 1989 1 46

[7] Cucker, F., Montaã±A, J. L., Pardo, L. M. Time bounded computations over the reals Internat. J. Algebra Comput. 1992 395 408

[8] Cucker, F., Montaã±A, J. L., Pardo, L. M. Models for parallel computation with real numbers 1995 53 63

[9] Cook, Stephen A. A taxonomy of problems with fast parallel algorithms Inform. and Control 1985 2 22

[10] Dedieu, Jean-Pierre Estimations for the separation number of a polynomial system J. Symbolic Comput. 1997 683 693

[11] Dedieu, Jean-Pierre Newton’s method and some complexity aspects of the zero-finding problem 2001 45 67

[12] Du, Ding-Zhu, Ko, Ker-I Theory of computational complexity 2000

[13] Elezoviä‡, Neven, Giordano, Carla, Pecì†Ariä‡, Josip The best bounds in Gautschi’s inequality Math. Inequal. Appl. 2000 239 252

[14] Federer, Herbert Geometric measure theory 1969

[15] Ho, Chung Wu A note on proper maps Proc. Amer. Math. Soc. 1975 237 241

[16] Hubbard, John, Schleicher, Dierk, Sutherland, Scott How to find all roots of complex polynomials by Newton’s method Invent. Math. 2001 1 33

[17] Kim, Myong-Hi Topological complexity of a root finding algorithm J. Complexity 1989 331 344

[18] Koiran, Pascal Hilbert’s Nullstellensatz is in the polynomial hierarchy J. Complexity 1996 273 286

[19] Malajovich, Gregorio On generalized Newton algorithms: quadratic convergence, path-following and error analysis Theoret. Comput. Sci. 1994 65 84

[20] Miller, Gary L. Riemann’s hypothesis and tests for primality J. Comput. System Sci. 1976 300 317

[21] Montaã±A, J. L., Pardo, Luis M. On Kolmogorov complexity in the real Turing machine setting Inform. Process. Lett. 1998 81 86

[22] Malajovich, Gregorio, Rojas, J. Maurice Polynomial systems and the momentum map 2002 251 266

[23] Rabin, Michael O. Probabilistic algorithm for testing primality J. Number Theory 1980 128 138

[24] Renegar, J. On the efficiency of Newton’s method in approximating all zeros of a system of complex polynomials Math. Oper. Res. 1987 121 148

[25] Shub, Michael Some remarks on Bezout’s theorem and complexity theory 1993 443 455

[26] Smale, Steve Newton’s method estimates from data at one point 1986 185 196

[27] Solovay, R., Strassen, V. A fast Monte-Carlo test for primality SIAM J. Comput. 1977 84 85

[28] Solovay, R., Strassen, V. Erratum: “A fast Monte-Carlo test for primality” (SIAM J. Comput. 6 (1977), no. 1, 84–85) SIAM J. Comput. 1978 118

[29] Shub, Michael, Smale, Steve Complexity of Bézout’s theorem. I. Geometric aspects J. Amer. Math. Soc. 1993 459 501

[30] Shub, M., Smale, S. Complexity of Bezout’s theorem. II. Volumes and probabilities 1993 267 285

[31] Shub, Michael, Smale, Steve Complexity of Bezout’s theorem. III. Condition number and packing J. Complexity 1993 4 14

[32] Shub, M., Smale, S. Complexity of Bezout’s theorem. V. Polynomial time Theoret. Comput. Sci. 1994 141 164

[33] Shub, Michael, Smale, Steve Complexity of Bezout’s theorem. IV. Probability of success SIAM J. Numer. Anal. 1996 128 148

[34] Yakoubsohn, Jean-Claude A universal constant for the convergence of Newton’s method and an application to the classical homotopy method Numer. Algorithms 1995 223 244