On a problem posed by Steve Smale (Q661924): Difference between revisions

\textit{S. Smale} [Math. Intell. 20, No.~2, 7--15 (1998; Zbl 0947.01011)] posted 18 mathematical problems for the 21st century. The 17th problem asks for the existence of a deterministic algorithm computing an approximate solution of a system of \(n\) complex polynomials in \(n\) unknowns in polynomial time, on the average, in the size \(N\) of the input system. \textit{C. Beltrán} and \textit{L. M. Pardo} [London Mathematical Society Lecture Note Series 331, 1--35 (2006; Zbl 1107.65316)] gave a partial solution to the problem by proposing a randomized algorithm. The aim of the paper is to extend their results. Using a linear homotopy algorithm and a smoothed and condition-based analysis, the authors exhibit a deterministic algorithm and show that its complexity is \(N^{\mathcal{O}(\log\log N)}\). The result is a nearly solution to Smale's 17th problem.