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 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, ()
[7] Morgan, F., Geometric measure theory, ()
[8] Priest, D., On properties of floating point arithmetics: numerical stability and cost of accurate computations, ()
[9] Shub, M., On the work of steve Smale on the theory of computation, (), 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, (), 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., to appear. · 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, (), 172-195, Berkeley, CA
[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, () · Zbl 0810.53057
[19] Sautalo, L.A., Integral geometry and geometric probability, (1976), Addison-Wesley Reading, MA
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.