COMPLEXITY OF BEZOUT-THEOREM-V - POLYNOMIAL-TIME

Authors
SHUB M SMALE S
Citation
M. Shub et S. Smale, COMPLEXITY OF BEZOUT-THEOREM-V - POLYNOMIAL-TIME, Theoretical computer science, 133(1), 1994, pp. 141-164
Citations number
19
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
133
Issue
1
Year of publication
1994
Pages
141 - 164
Database
ISI
SICI code
0304-3975(1994)133:1<141:COB-P>2.0.ZU;2-9
Abstract
We show that there are algorithms which find an approximate zero of a system of polynomial equations and which function in polynomial time o n the average. The number of arithmetic operations is cN(4s), where N is the input size and c a universal constant.