On a Problem Posed by Steve Smale TeX Export

@article{citeulike:5779895, abstract = {The 17th of the problems proposed by Steve Smale for the 21st century asks for the existence of a deterministic algorithm computing an approximate solution of a system of \$n\$ complex polynomials in \$n\$ unknowns in time polynomial, on the average, in the size \$N\$ of the input system. A partial solution to this problem was given by Carlos Beltran and Luis Miguel Pardo who exhibited a randomized algorithm doing so. In this paper we further extend this result in several directions. Firstly, we exhibit a linear homotopy algorithm that efficiently implements a non-constructive idea of Mike Shub. This algorithm is then used in a randomized algorithm, call it LV, a la Beltran-Pardo. Secondly, we perform a smoothed analysis (in the sense of Spielman and Teng) of algorithm LV and prove that its smoothed complexity is polynomial in the input size and \$\s^{-1}\$, where \$\s\$ controls the size of of the random perturbation of the input systems. Thirdly, we perform a condition-based analysis of LV. That is, we give a bound, for each system \$f\$, of the expected running time of LV with input \$f\$. In addition to its dependence on \$N\$ this bound also depends on the condition of \$f\$. Fourthly, and to conclude, we return to Smale's 17th problem as originally formulated for deterministic algorithms. We exhibit such an algorithm and show that its average complexity is \$N^{O(\log\log N)}\$. This is nearly a solution to Smale's 17th problem.}, archivePrefix = {arXiv}, author = {Buergisser, Peter and Cucker, Felipe}, citeulike-article-id = {5779895}, citeulike-linkout-0 = {http://arxiv.org/abs/0909.2114}, citeulike-linkout-1 = {http://arxiv.org/pdf/0909.2114}, day = {11}, eprint = {0909.2114}, keywords = {algorithm, complexity, polynomial}, month = {Sep}, posted-at = {2009-09-14 07:38:56}, priority = {2}, title = {On a Problem Posed by Steve Smale}, url = {http://arxiv.org/abs/0909.2114}, year = {2009} }

TY - JOUR ID - citeulike:5779895 L3 - citeulike-article-id:5779895 N2 - The 17th of the problems proposed by Steve Smale for the 21st century asks for the existence of a deterministic algorithm computing an approximate solution of a system of $n$ complex polynomials in $n$ unknowns in time polynomial, on the average, in the size $N$ of the input system. A partial solution to this problem was given by Carlos Beltran and Luis Miguel Pardo who exhibited a randomized algorithm doing so. In this paper we further extend this result in several directions. Firstly, we exhibit a linear homotopy algorithm that efficiently implements a non-constructive idea of Mike Shub. This algorithm is then used in a randomized algorithm, call it LV, a la Beltran-Pardo. Secondly, we perform a smoothed analysis (in the sense of Spielman and Teng) of algorithm LV and prove that its smoothed complexity is polynomial in the input size and $\s^{-1}$, where $\s$ controls the size of of the random perturbation of the input systems. Thirdly, we perform a condition-based analysis of LV. That is, we give a bound, for each system $f$, of the expected running time of LV with input $f$. In addition to its dependence on $N$ this bound also depends on the condition of $f$. Fourthly, and to conclude, we return to Smale's 17th problem as originally formulated for deterministic algorithms. We exhibit such an algorithm and show that its average complexity is $N^{O(\log\log N)}$. This is nearly a solution to Smale's 17th problem. TI - On a Problem Posed by Steve Smale KW - algorithm KW - complexity KW - polynomial AU - Buergisser, Peter AU - Cucker, Felipe PY - 2009/Sep/11/ UR - http://arxiv.org/abs/0909.2114 ER -