On a problem posed by Steve Smale (Q661924): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 09:53, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On a problem posed by Steve Smale |
scientific article |
Statements
On a problem posed by Steve Smale (English)
0 references
11 February 2012
0 references
\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.
0 references
polynomial equation solving
0 references
approximate zero
0 references
complexity
0 references
linear homotopy algorithm
0 references
polynomial time
0 references
smoothed analysis
0 references
deterministic algorithm
0 references
complex polynomials
0 references
randomized algorithm
0 references