On Smale's 17th problem: a probabilistic positive solution

DOI10.1007/s10208-005-0211-0zbMath1153.65048OpenAlexW2138739352WikidataQ56697969 ScholiaQ56697969MaRDI QIDQ937276

Luis Miguel Pardo, Carlos Beltran

Publication date: 20 August 2008

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10208-005-0211-0

zbMATH Keywords

Computational complexityApproximate zero theoryProbabilistic polynomial timeProjective algebraic varietySystem of equations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical computation of solutions to systems of equations (65H10) Global methods, including homotopy approaches to the numerical solution of nonlinear equations (65H20) Integration on manifolds; measures on manifolds (58C35) Randomized algorithms (68W20)

Related Items

Certified Numerical Homotopy Tracking, Random sampling in computational algebra: Helly numbers and violator spaces, Functional norms, condition numbers and numerical algorithms in algebraic geometry, On the zeta Mahler measure function of the Jacobian determinant, condition numbers and the height of the generic discriminant, On the geometry and topology of the solution variety for polynomial system solving, Condition numbers for the cube. I: Univariate polynomials and hypersurfaces, A continuation method to solve polynomial systems and its complexity, Rigid continuation paths II. structured polynomial systems, Learning a performance metric of Buchberger's algorithm, Certified predictor-corrector tracking for Newton homotopies, Fast linear homotopy to find approximate zeros of polynomial systems, Robust certified numerical homotopy tracking, An arithmetic Poisson formula for the multi-variate resultant, 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, Fast computation of zeros of polynomial systems with bounded degree under finite-precision, On the probability distribution of data at points in real complete intersection varieties, Foreword. What is numerical algebraic geometry?, A note on the finite variance of the averaging function for polynomial system solving, Smale’s 17th problem: Average polynomial time to compute affine and projective solutions, Smale 17th Problem: Advances and Open Directions, A promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and density, Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems, Complexity of Bezout's theorem. VI: Geodesics in the condition (number) metric

Uses Software

• MultRoot
• mctoolbox