Smale’s 17th problem: Average polynomial time to compute affine and projective solutions

Source abstract

Smale’s 17th problem asks: “Can a zero of n n complex polynomial equations in n n unknowns be found approximately, on the average, in polynomial time with a uniform algorithm?” We give a positive answer to this question. Namely, we describe a uniform probabilistic algorithm that computes an approximate zero of systems of polynomial equations f : C n ⟶ C n f:\mathbb {C}^n\longrightarrow \mathbb {C}^n , performing a number of arithmetic operations which is polynomial in the size of the input, on the average.