The 17th of the problems proposed by Steve Smale for the 21st century asks
for the existence of a deterministic algorithm computing an approximate
solution of a system of $n$ complex polynomials in $n$ unknowns in time
polynomial, on the average, in the size $N$ of the input system. A partial
solution to this problem was given by Carlos Beltran and Luis Miguel Pardo who
exhibited a randomized algorithm doing so. In this paper we further extend this
result in several directions. Firstly, we exhibit a linear homotopy algorithm
that efficiently implements a non-constructive idea of Mike Shub.