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

Abstract

Smale’s 17th problem asks: “Can a zero of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> complex polynomial equations in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> 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 <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="f colon double-struck upper C Superscript n Baseline long right-arrow double-struck upper C Superscript n"> <mml:semantics> <mml:mrow> <mml:mi>f</mml:mi> <mml:mo>:</mml:mo> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">C</mml:mi> </mml:mrow> <mml:mi>n</mml:mi> </mml:msup> <mml:mo stretchy="false">⟶</mml:mo> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">C</mml:mi> </mml:mrow> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">f:\mathbb {C}^n\longrightarrow \mathbb {C}^n</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, performing a number of arithmetic operations which is polynomial in the size of the input, on the average.