On Smale's 17th Problem: A Probabilistic Positive Solution
On Smale's 17th Problem: A Probabilistic Positive Solution
复制标题
论斯梅尔第十七题：概率正解
DOI：
10.1007/s10208-005-0211-0
复制
发表时间：
2008
影响因子：
3
通讯作者：
L. M. Pardo
中科院分区：
文献类型：
--
作者：
C. Beltrán;L. M. Pardo
斯梅尔的第17个问题问道：“能用统一的算法在多项式时间内平均找到n个未知数中n个复多项式的零点吗？”给出了该问题的统一概率算法，并证明了算法的复杂性是多项式的。由此，我们得到了斯梅尔第17问题的部分正解。
Smale's 17th Problem asks “Can a zero of n complex polynomial equations in n unknowns be found approximately, on the average [for a suitable probability measure on the space of inputs], in polynomial time with a uniform algorithm?” We present a uniform probabilistic algorithm for this problem and prove that its complexity is polynomial. We thus obtain a partial positive solution to Smale's 17th Problem.
影响因子：
2.1
作者：
通讯作者：
--