When faced with a hard problem—that cannot be ignored—one natural ap-
proach to deal with it is...
(1) Prove that the problem has instances that are hard in some rigorous
computational sense, i.e., “worst-case” instances.
(2) Given success with (1), classify the worst-case instances.
(3) Given success with (2), find an algorithm that is provably fast, away from
Algebraic geometers, complexity theorists, numerical analysts, optimization
experts, physicists, and probabilists have each come across these tactics in their
own way. The volume you are reading now focuses on the setting of systems of
polynomial equations, primarily from the point of view of numerical computation
and algebraic geometry.
Perhaps the most elegant statement unifying these two subjects is Smale’s 17th
Problem, first stated in June 1997:
Can a zero of n complex polynomial equations in n unknowns be
found approximately, on the average, in polynomial time with a
The statement of the problem artfully highlights the hardness of polynomial
system solving: polynomial systems usually have a number of complex solutions
exponential in n; hence “a zero” instead of “all zeroes”. More to the point, the
theory of NP-hardness tells us that merely deciding the existence of a complex
solution is already hard. So what hope have we of fast solving? Enter
randomization: Smale foresaw the possibility that equations that are hard to solve
are rare; hence “on the average”.
During Febuary 28 – March 5 (2010), a 5 day workshop on Randomization,
Relaxation, and Complexity (organized by Leonid Gurvits, Pablo Parrilo, and J.
Maurice Rojas) took place at the Banff International Research Station, and the
papers here are the fruit of this workshop. One of the goals of this workshop was to
bring together some of the diverse communities that use and advance polynomial
system solving. Indeed, the papers are closely interrelated: (Beltr´ an & Pardo)
details recent advances toward solving Smale’s 17th Problem, while (Avenda˜ no &
Ibrahim) and (Bastani, Hillar, Popov, & Rojas) deal with a tropical geometric
approach toward the kind of averaging alluded to in Smale’s 17th Problem. The
papers (Bates, Hauenstein, & Sommese), (Lee & Li), (Leykin), and (Zeng) apply
and develop theory to bring practical polynomial solver performance closer to that
sought by Smale’s 17th Problem. The papers (Grenet, Kaltofen, Koiran, & Portier),
(Nisse), and (Rusek, Shakalli, & Sottile) deal with complexity issues (geometric
and/or computational) that are fundamental in the solution of polynomial systems.