Condition length and complexity for the solution of polynomial systems

Smale’s 17th problem asks for an algorithm which finds an approximate zero of polynomial systems in average polynomial time (see Smale 2000). The main progress on Smale’s problem is Beltr'an-Pardo (2011) and B"urgisser-Cucker (2010). In this paper we will improve on both approaches and we prove an important intermediate result. Our main results are Theorem 1 on the complexity of a randomized algorithm which improves the result of Beltr'an-Pardo (2011), Theorem 2 on the average of the condition number of polynomial systems which improves the estimate found in B"urgisser-Cucker (2010), and Theorem 3 on the complexity of finding a single zero of polynomial systems. This last Theorem is the main result of B"urgisser-Cucker (2010). We give a proof of it relying only on homotopy methods, thus removing the need for the elimination theory methods used in B"urgisser-Cucker (2010). We build on methods developed in Armentano et al. (2015).