On Smale's 17th problem: a probabilistic positive solution (Q937276): Difference between revisions

\textit{M. Shub} and \textit{S. Smale}, in the series of five papers ``Complexity of Bezout's Theorem I-V'' [part I, J. Am. Math. Soc. 6, No. 2, 459--501 (1993; Zbl 0821.65035); part II in: Eyssette, Frédéric et al., Computational algebraic geometry. Papers from a conference, held in Nice, France, April 21-25, 1992. Boston: Birkhäuser. Prog. Math. 109, 267--285 (1993; Zbl 0851.65031); part III, J. Complexity 9, No. 1, 4--14 (1993; Zbl 0846.65018); part IV, SIAM J. Numer. Anal. 33, No. 1, 128--148 (1996; Zbl 0843.65035); part V, Theor. Comput. Sci. 133, No. 1, 141--164 (1994; Zbl 0846.65022)], studied the ``features that distinguish the tractable from the intractable in the realm of solving polynomial systems of equations.'' Based on these studies, 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?'' In the fifth paper [loc. cit.], Shub and Smale found such a procedure, but the algorithm is different for each degree vector of the polynomials. A uniform algorithm is one that is independent of the degree. In the present work, the authors found a probabilistic uniform algorithm for the problem and prove that its complexity is polynomial, obtaining a partial positive answer to Smale's 17th problem. To set the notation, the authors consider the set \(\mathcal{H}_{(d)}\) of all systems \(f:=(f_1, \ldots, f_n)\) of homogeneous polynomials of respective degrees \((d):=(d_1, \ldots ,d_n) \in \mathbb{N}^n\). If \(N+1\) is the complex dimension of the vector space \(\mathcal{H}_{(d)}\), and if \(d=\max d_i\), then the authors prove that there is bounded error probabilistic numerical analysis procedure that solve most systems of multivariate homogeneous polynomial equations with running time polynomial in \(n, N\) and \(d\). Moreover, they show that the probability that a randomly chosen system \(f \in \mathcal{H}_{(d)}\) is solved by the procedure is greater than \(1 - \frac{1}{N}\). The algorithm developed by the authors is based on homotopic deformation and belongs to the family of ``nonuniversal polynomial equation solvers''. It consists of 43 pages with 61 references. Using Smale's words, ``finding zeros of polynomials and polynomial systems is one of the oldest and most central problems of mathematics. Our problem asks if, under some conditions specialized in the problem, it can be solved systematically by computers. If there is no polynomial time way of doing it, then no computer will ever succeed.'' This paper is an important milestone leading to a positive solution to this fundamental mathematical quest.