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 in Mathematical problems for the next century, American Mathematical Society, Providence, 2000). The main progress on Smale's problem is Beltran and Pardo (Found Comput Math 11(1):95-129, 2011) and Burgisser and Cucker (Ann Math 174(3):1785-1836, 2011). In this paper, we will improve on both approaches and prove an interesting intermediate result on the average value of the condition number. Our main results are Theorem 1 on the complexity of a randomized algorithm which improves the result of Beltran and Pardo (2011), Theorem 2 on the average of the condition number of polynomial systems which improves the estimate found in Burgisser and Cucker (2011), and Theorem 3 on the complexity of finding a single zero of polynomial systems. This last theorem is similar to the main result of Burgisser and Cucker (2011) but relies only on homotopy methods, thus removing the need for the elimination theory methods used in Burgisser and Cucker (2011). We build on methods developed in Armentano et al. (2014).