An interesting problem in non-linear algebra is Smale's 17th problem, which can be stated as follows: “Can a zero of n complex polynomial equations in n unknowns be found approximately, on the average in polynomial time with a uniform algorithm?”
The research challenge is to find a deterministic algorithm. Some probabilistic algorithms have been proposed in the mathematics literature.
I like to know the status of research on Smale's 17th problem. Thanks!
I think the problem is solved. See:
C. Beltrán, Luis M. Pardo, Smale's 17th Problem: Average Polynomial Time to Compute Affine and Projective Solutions. Journal of the Amer. Math. Soc. 22 (2009), 363-385.
Dear Prof. M.V. Carriegos: As I understand, Beltran & Pardo have given a "partial solution" to Smale's 17th problem. Please see the link, which comments on Beltran's solution..
http://arxiv.org/abs/0909.2114
Smale's problems are a list of 18 challenging problems for the twenty-first century proposed by Field medalist Steven Smale. These problems were inspired in part by Hilbert's famous list of problems presented in 1900 (Hilbert's problems), and in part in response to a suggestion by V. I. Arnold on behalf of the International Mathematical Union that mathematicians describe a number of outstanding problems for the 21st century.
http://mathworld.wolfram.com/SmalesProblems.html
The algorithm described by Beltran and Pardo is a randomized algoritm. Finding a deterministic one is still an open problem.
See C. Beltrán, Michael Shub, "The complexity and geometry of numerically solving polynomial systems". Contemporary Mathematics, volume 604, 2013, pp 71-104.
for a recent and complete state of the art on the subject. The paper is available on the Carlos Beltran page.
- Badges
- Science topic
- Similar topics
- Mathematics