×

On a problem posed by Steve Smale. (English) Zbl 1248.65047

S. Smale [Math. Intell. 20, No. 2, 7–15 (1998; Zbl 0947.01011)] posted 18 mathematical problems for the 21st century. The 17th problem asks for the existence of a deterministic algorithm computing an approximate solution of a system of \(n\) complex polynomials in \(n\) unknowns in polynomial time, on the average, in the size \(N\) of the input system. C. Beltrán and L. M. Pardo [London Mathematical Society Lecture Note Series 331, 1–35 (2006; Zbl 1107.65316)] gave a partial solution to the problem by proposing a randomized algorithm. The aim of the paper is to extend their results. Using a linear homotopy algorithm and a smoothed and condition-based analysis, the authors exhibit a deterministic algorithm and show that its complexity is \(N^{\mathcal{O}(\log\log N)}\). The result is a nearly solution to Smale’s 17th problem.

MSC:

65H04 Numerical computation of roots of polynomial equations
65H10 Numerical computation of solutions to systems of equations
65Y20 Complexity and performance of numerical algorithms
65E05 General theory of numerical methods in complex analysis (potential theory, etc.)
30C15 Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral)
30C10 Polynomials and rational functions of one complex variable

References:

[1] M. Agrawal, N. Kayal, and N. Saxena, ”PRIMES is in P,” Ann. of Math., vol. 160, iss. 2, pp. 781-793, 2004. · Zbl 1071.11070 · doi:10.4007/annals.2004.160.781
[2] D. Amelunxen and P. Bürgisser, ”Robust smoothed analysis of a condition number of linear programming,” Math. Program., Ser. A. · Zbl 1242.90098 · doi:10.1007/s10107-010-0346-x
[3] W. Baur and V. Strassen, ”The complexity of partial derivatives,” Theoret. Comput. Sci., vol. 22, iss. 3, pp. 317-330, 1983. · Zbl 0498.68028 · doi:10.1016/0304-3975(83)90110-X
[4] C. Beltrán and L. M. Pardo, ”On Smale’s 17th problem: a probabilistic positive solution,” Found. Comput. Math., vol. 8, iss. 1, pp. 1-43, 2008. · Zbl 1153.65048 · doi:10.1007/s10208-005-0211-0
[5] C. Beltrán and L. M. Pardo, ”Smale’s 17th problem: average polynomial time to compute affine and projective solutions,” J. Amer. Math. Soc., vol. 22, iss. 2, pp. 363-385, 2009. · Zbl 1206.90173 · doi:10.1090/S0894-0347-08-00630-9
[7] C. Beltrán and M. Shub, ”Complexity of Bezout’s theorem. VII. Distance estimates in the condition metric,” Found. Comput. Math., vol. 9, iss. 2, pp. 179-195, 2009. · Zbl 1175.65058 · doi:10.1007/s10208-007-9018-5
[8] L. Blum, F. Cucker, M. Shub, and S. Smale, Complexity and Real Computation, New York: Springer-Verlag, 1998. · Zbl 0872.68036 · doi:10.1142/S0218127496001818
[9] 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., vol. 21, iss. 1, pp. 1-46, 1989. · Zbl 0681.03020 · doi:10.1090/S0273-0979-1989-15750-9
[10] P. Bürgisser and F. Cucker, ”Smoothed analysis of Moore-Penrose inversion,” SIAM J. Matrix Anal. Appl., vol. 31, iss. 5, pp. 2769-2783, 2010. · Zbl 1227.65035 · doi:10.1137/100782954
[11] P. Bürgisser, F. Cucker, and M. Lotz, ”Smoothed analysis of complex conic condition numbers,” J. Math. Pures Appl., vol. 86, iss. 4, pp. 293-309, 2006. · Zbl 1113.65044 · doi:10.1016/j.matpur.2006.06.001
[12] P. Bürgisser, F. Cucker, and M. Lotz, ”The probability that a slightly perturbed numerical analysis problem is difficult,” Math. Comp., vol. 77, iss. 263, pp. 1559-1583, 2008. · Zbl 1195.65018 · doi:10.1090/S0025-5718-08-02060-7
[13] K. P. Choi, ”On the medians of gamma distributions and an equation of Ramanujan,” Proc. Amer. Math. Soc., vol. 121, iss. 1, pp. 245-251, 1994. · Zbl 0803.62007 · doi:10.2307/2160389
[14] F. Cucker, H. Diao, and Y. Wei, ”Smoothed analysis of some condition numbers,” Numer. Linear Algebra Appl., vol. 13, iss. 1, pp. 71-84, 2006. · Zbl 1198.65084 · doi:10.1002/nla.464
[15] F. Cucker, R. Hauser, and M. Lotz, ”Adversarial smoothed analysis,” J. Complexity, vol. 26, iss. 3, pp. 255-262, 2010. · Zbl 1232.65071 · doi:10.1016/j.jco.2009.12.005
[16] R. Howard, ”The kinematic formula in Riemannian homogeneous spaces,” Mem. Amer. Math. Soc., vol. 106, iss. 509, p. vi, 1993. · Zbl 0810.53057
[17] M. O. Rabin, ”Probabilistic algorithm for testing primality,” J. Number Theory, vol. 12, iss. 1, pp. 128-138, 1980. · Zbl 0426.10006 · doi:10.1016/0022-314X(80)90084-0
[18] J. Renegar, ”On the worst-case arithmetic complexity of approximating zeros of systems of polynomials,” SIAM J. Comput., vol. 18, iss. 2, pp. 350-370, 1989. · Zbl 0676.65045 · doi:10.1137/0218024
[19] A. Sankar, D. A. Spielman, and S. Teng, ”Smoothed analysis of the condition numbers and growth factors of matrices,” SIAM J. Matrix Anal. Appl., vol. 28, iss. 2, pp. 446-476, 2006. · Zbl 1179.65033 · doi:10.1137/S0895479803436202
[20] M. Shub, ”Some remarks on Bezout’s theorem and complexity theory,” in From Topology to Computation: Proceedings of the Smalefest, New York: Springer-Verlag, 1993, pp. 443-455. · Zbl 0811.13021
[21] M. Shub, ”Complexity of Bezout’s theorem. VI. Geodesics in the condition (number) metric,” Found. Comput. Math., vol. 9, iss. 2, pp. 171-178, 2009. · Zbl 1175.65060 · doi:10.1007/s10208-007-9017-6
[22] M. Shub and S. Smale, ”Complexity of Bézout’s theorem. I. Geometric aspects,” J. Amer. Math. Soc., vol. 6, iss. 2, pp. 459-501, 1993. · Zbl 0821.65035 · doi:10.2307/2152805
[23] M. Shub and S. Smale, ”Complexity of Bezout’s theorem. II. Volumes and probabilities,” in Computational Algebraic Geometry, Boston, MA: Birkhäuser, 1993, vol. 109, pp. 267-285. · Zbl 0851.65031 · doi:10.1006/jcom.1993.1002
[24] M. Shub and S. Smale, ”Complexity of Bezout’s theorem. III. Condition number and packing,” J. Complexity, vol. 9, iss. 1, pp. 4-14, 1993. · Zbl 0846.65018 · doi:10.1006/jcom.1993.1002
[25] M. Shub and S. Smale, ”Complexity of Bezout’s theorem. IV. Probability of success; extensions,” SIAM J. Numer. Anal., vol. 33, iss. 1, pp. 128-148, 1996. · Zbl 0843.65035 · doi:10.1137/0733008
[26] M. Shub and S. Smale, ”Complexity of Bezout’s theorem. V. Polynomial time,” Theoret. Comput. Sci., vol. 133, iss. 1, pp. 141-164, 1994. · Zbl 0846.65022 · doi:10.1016/0304-3975(94)90122-8
[27] S. Smale, ”Newton’s method estimates from data at one point,” in The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics, New York: Springer-Verlag, 1986, pp. 185-196. · Zbl 0613.65058
[28] S. Smale, ”Complexity theory and numerical analysis,” in Acta Num., Cambridge: Cambridge Univ. Press, 1997, vol. 6, pp. 523-551. · Zbl 0883.65125
[29] S. Smale, ”Mathematical problems for the next century,” in Mathematics: Frontiers and Perspectives, Providence, RI: Amer. Math. Soc., 2000, pp. 271-294. · Zbl 1031.00005
[30] R. Solovay and V. Strassen, ”A fast Monte-Carlo test for primality,” SIAM J. Comput., vol. 6, iss. 1, pp. 84-85, 1977. · Zbl 0345.10002 · doi:10.1137/0206006
[31] D. A. Spielman and S. Teng, ”Smoothed analysis of algorithms,” in Proceedings of the International Congress of Mathematicians, Vol. I, Beijing, 2002, pp. 597-606. · Zbl 1056.65148
[32] D. A. Spielman and S. Teng, ”Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time,” J. ACM, vol. 51, iss. 3, pp. 385-463, 2004. · Zbl 0563.03027 · doi:10.1145/990308.990310
[33] M. Wschebor, ”Smoothed analysis of \(\kappa(A)\),” J. Complexity, vol. 20, iss. 1, pp. 97-107, 2004. · Zbl 1065.15029 · doi:10.1016/j.jco.2003.09.003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.