This volume is composed of six contributions derived from the lectures given
during the UIMP–RSME Llu´ ıs Santal´ o Summer School on “Recent Advances in
Real Complexity and Computation”. The goal of this Summer School was to present
some of the recent advances on Smale’s 17th Problem. This Problem was stated by
Steve Smale as follows:
Problem 1 (Smale’s 17th Problem). Can a zero of n complex polynomial equa-
tions in n unknowns be found approximately, on the average, in polynomial time
with a uniform algorithm?
These contributions cover several aspects around this problem: from numerical
to symbolic methods in polynomial equation solving, computational complexity as-
pects (both worse and average cases, both upper and lower complexity bounds) and
even aspects of the underlying geometry of the problem. Some of the contributions
also deal with either real or multiple solutions solving.
The School was oriented to graduate mathematicians, as to Master or Ph. D.
students in Mathematics and to senior researchers interested on this topic.
The School was promoted and supported by the Spanish Royal Mathematical
Society (RSME) and hosted by the Universidad Internacional Men´ endez Pelayo
(UIMP), from July 16th to July 20th of 2012, in El Palacio de la Magdalena, San-
tander. Partial financial support was also granted by the University of Cantabria
and the Spanish Ministry of Science Grant MTM2010-16051. We thank these in-
stitutions and grants for their financial support.
The speakers (in alphabetical order) and their courses in this Summer School
were the following ones:
• Carlos Beltr´ an,“Stability, precision and complexity in some numerical
• Marc Giusti, “Polar, co–polar and bipolar varieties: real solving of alge-
braic varieties with intrinsic complexity”.
• Joos Heintz, “On the intrinsic complexity of elimination problems in ef-
fective algebraic geometry”.
• Gregorio Malajovich, “From the quadratic convergence of Newton’s method
to problems of counting of the number of solutions”.
• Klaus Meer,“Real Number Complexity Theory and Probabilistically Check-
able Proofs (PCPs)”.
• Michael Shub,“The geometry of condition and the analysis of algorithms”.
• Jean-Claude Yakoubsohn, “ Tracking multiplicities”.