Complexity of Bezout’s theorem. V: Polynomial time. (English) Zbl 0846.65022

Summary: [For part III see J. Complexity 9, No. 1, 4-14 (1993; Zbl 0846.65018). For part IV see SIAM J. Numer. Anal. 33, No. 1, 128-148 (1996; Zbl 0843.65035).]
We show that there are algorithms which find an approximate zero of a system of polynomial equations and which function in polynomial time on the average. The number of arithmetic operations is \(cN^{4s}\), where \(N\) is the input size and \(c\) a universal constant.


65H10 Numerical computation of solutions to systems of equations
12Y05 Computational aspects of field theory and polynomials (MSC2010)
65Y20 Complexity and performance of numerical algorithms
30C15 Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral)
Full Text: DOI


[1] Blum, L.; Shub, M.; Smale, S., On a theory of computation and complexity over the real numbers: NP-completeness, Recursive functions and Universal Machines, Bull. Amer. Math. Soc., 21, 1-46 (1989) · Zbl 0681.03020
[2] Cucker, F.; Shub, M.; Smale, S., Separation of Complexity classes in Koiran’s weak model (1993), preprint · Zbl 0819.68053
[3] Kim, M.-H., Error analysis and bit complexity: polynomial root finding problem, Part I (1988), Bellcore: Bellcore Morristown, NJ, preprint
[4] Koiran, P., A weak version of the Blum, Shub and Smale model, 34th Found. of Comp. Sci., 486-495 (1993)
[5] Kostlan, E., Random polynomials and the statistical fundamental theorem of algebra (1987), Univ. of Hawaii, preprint
[6] Malajovich-Muñoz, G., On the complexity of path-following Newton algorithms for solving systems of polynomial equations with integer coefficients, (Ph.D. Thesis (1993), University of California at Berkeley)
[7] Morgan, F., Geometric Measure Theory, (A Beginners Guide (1988), Academic Press: Academic Press New York) · Zbl 0671.49043
[8] Priest, D., On properties of floating point arithmetics: numerical stability and cost of accurate computations, (Ph.D. Thesis (1992), University of California at Berkeley)
[9] Shub, M., On the work of Steve Smale on the theory of computation, (Hirsch, M.; Marsden, J.; Shub, M., Topology to Computation: Proceedings of the Smalefest (1993), Springer: Springer Berlin), 281-301 · Zbl 0812.68041
[10] Shub, M.; Smale, S., Computational complexity, on the geometry of polynomials and a theory of cost: Part II, SIAM J. Comput., 15, 145-161 (1986) · Zbl 0625.65036
[11] Shub, M.; Smale, S., Complexity of Bezout’s theorem I: Geometric aspects, J. Amer. Math. Soc., 6, 459-501 (1993) · Zbl 0821.65035
[12] Shub, M.; Smale, S., Complexity of Bezout’s theorem II: Volumes and probabilities, (Eyssette, F.; Galligo, A., Computational Algebraic Geometry, Progress in Mathematics, Vol. 109 (1993), Birkhäuser: Birkhäuser Basel), 267-285 · Zbl 0851.65031
[13] Shub, M.; Smale, S., Complexity of Bezout’s theorem III: Condition number and packing, J. Complexity, 9, 4-14 (1993) · Zbl 0846.65018
[14] M. Shub and S. Smale, Complexity and Bezout’s theorem IV: Probability of Success, Extensions, SIAM J. Numer. Anal.; M. Shub and S. Smale, Complexity and Bezout’s theorem IV: Probability of Success, Extensions, SIAM J. Numer. Anal. · Zbl 0843.65035
[15] Smale, S., The fundamental theorem of algebra and complexity theory, Bull. Amer. Math. Soc., 4, 1-36 (1981), (N.S.) · Zbl 0456.12012
[16] Smale, S., Algorithms for solving equations, (Proc. Internat. Congr. Mathematicians (1986), American Mathematical Society: American Mathematical Society Providence, RI), 172-195, Berkeley, CA · Zbl 0665.65058
[17] Smale, S., Some remarks on the foundations of numerical analysis, SIAM Rev., 32, 211-220 (1990) · Zbl 0703.65003
[18] Howard, R., The Kinematic Formula in Riemannian Homogeneous Spaces, (Memoirs of the AMS, Vol. 509 (1993), AMS: AMS Providence, RI) · Zbl 0810.53057
[19] Sautalo, L. A., Integral Geometry and Geometric Probability (1976), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0342.53049
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.