On Smale's 17th problem: a probabilistic positive solution
Approximate zero theoryComputational complexityProbabilistic polynomial timeProjective algebraic varietySystem of equations
Integration on manifolds; measures on manifolds (58C35) Numerical computation of solutions to systems of equations (65H10) Global methods, including homotopy approaches to the numerical solution of nonlinear equations (65H20) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)
\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.
- A faster solution to Smale's 17th problem. I: Real binomial systems
- Smale's 17th problem: average polynomial time to compute affine and projective solutions
- Numerically determining solutions of systems of polynomial equations
- On a problem posed by Steve Smale
- Rigid continuation paths II. structured polynomial systems
- Solving polynomial equations in smoothed polynomial time and a near solution to Smale's 17th problem
- Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems
- Condition length and complexity for the solution of polynomial systems
- Fast computation of zeros of polynomial systems with bounded degree under finite-precision
- scientific article; zbMATH DE number 5124810
- Complexity of Bezout's theorem. VI: Geodesics in the condition (number) metric
- Complexity of Bezout's theorem. V: Polynomial time
- On the geometry and topology of the solution variety for polynomial system solving
- Robust certified numerical homotopy tracking
- A promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and density
- A note on the finite variance of the averaging function for polynomial system solving
- An arithmetic Poisson formula for the multi-variate resultant
- Condition numbers for the cube. I: Univariate polynomials and hypersurfaces
- Random sampling in computational algebra: Helly numbers and violator spaces
- Certified numerical homotopy tracking
- Smale's 17th problem: average polynomial time to compute affine and projective solutions
- Nonlinear equations. Paper from the 28th Brazilian mathematics colloquium -- 28\(^{\text o}\) Colóquio Brasileiro de Matemática, Rio de Janeiro, Brazil, July 2011
- On the zeta Mahler measure function of the Jacobian determinant, condition numbers and the height of the generic discriminant
- Smale 17th Problem: Advances and Open Directions
- Smale's fundamental theorem of algebra reconsidered
- scientific article; zbMATH DE number 1859208 (Why is no real title available?)
- Functional norms, condition numbers and numerical algorithms in algebraic geometry
- Foreword. What is numerical algebraic geometry?
- A faster solution to Smale's 17th problem. I: Real binomial systems
- Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems
- Some remarks on Smale's “Algorithms for solving equations”
- Fast computation of zeros of polynomial systems with bounded degree under finite-precision
- Rigid continuation paths II. structured polynomial systems
- Learning a performance metric of Buchberger's algorithm
- A continuation method to solve polynomial systems and its complexity
- Fast linear homotopy to find approximate zeros of polynomial systems
- A numerical algorithm for zero counting. III: Randomization and condition
- Globally convergent, iterative path-following for algebraic equations
- On a problem posed by Steve Smale
- The work of Steve Smale
- Certified algebraic curve projections by path tracking
- Certified predictor-corrector tracking for Newton homotopies
- On the probability distribution of data at points in real complete intersection varieties
This page was built for publication: On Smale's 17th problem: a probabilistic positive solution
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q937276)
