x EDITORS’ PREFACE The present volume extends the Summer School by expository articles pre- senting the state of art of each of the topics. The reader will find the following contributions in forthcoming pages: (1) Martijn Baartse and Klaus Meer,“Topics in real and complex num- ber complexity theory” The contribution intends to introduce into topics relevant in real and com- plex number complexity theory. This is done in a survey style. Taking as starting point the computational model introduced by Blum, Shub, and Smale the following issues are addressed: Basic results concerning decid- ability and NP -completeness, transfer results of open questions between different models of computation, structural complexity inside NPR, com- putational universality, and probabilistically checkable proofs over the real and complex numbers. (2) Bernd Bank, Marc Giusti and Joos Heintz, “Polar, bipolar and copolar varieties: Real solving of algebraic varieties with intrinsic com- plexity”. This survey covers a decade and a half of joint work with L. Lehmann, G. M. Mbakop, and L. M. Pardo. The authors address the problem of finding a smooth algebraic sample point for each connected component of a real algebraic variety, being only interested in components which are generically smooth locally complete intersections. The complexity of their algorithms is essentially polynomial in the degree of suitably defined gen- eralized polar varieties and is therefore intrinsic to the problem under consideration. (3) Carlos Beltr´ and Michael Shub, “The complexity and geometry of numerical solving polynomial equations”. This contribution contains a short overview on the state of the art of efficient numerical analysis methods that solve systems of multivariate polynomial equations. The authors focus on the work of Steve Smale who initiated this research framework, and on the collaboration between Stephen Smale and Michael Shub, which set the foundations of this ap- proach to polynomial system–solving, culminating in the more recent ad- vances of Carlos Beltr´ an, Luis Miguel Pardo, Peter urgisser and Felipe Cucker. (4) Marc Giusti and Jean–Claude Yakoubsohn, “Multiplicity hunting and approximating multiple roots of polynomials systems”. The computation of the multiplicity and the approximation of isolated multiple roots of polynomial systems is a difficult problem. In recent years, there has been an increase of activity in this area. Our goal is to translate the theoretical background developed in the last century on the theory of singularities in terms of computation and complexity. This paper presents several different views that are relevant to address the following issues : predict the multiplicity of a root and/or determine the number of roots in a ball, approximate fast a multiple root and give complexity results for such problems. Finally, we propose a new method to determine a regular system, called equivalent but deflated, i.e., admitting the same root as the initial singular one.
Previous Page Next Page