Whereas classical complexity deals with problems over finite alphabets, many fundamental algorithms in mathematics are developed for uncountable domains like R and C. Think about Gaussian elimination, Newton's method and many more. Thus it seems reasonable to combine questions and methods from complexity theory with real number problems. This approach has been followed already a long time in algebraic complexity theory, where the complexity of problems in a fixed real space R^n is studied. In 1989 Blum, Shub, and Smale introduced a uniform model of computation and complexity over arbitrary rings with special emphasis on the field of real and complex numbers.

After introducing the basic concepts behind the above model we want to give some ideas how different fields of mathematics and computer science come into play when treating real number issues. This includes problems and methods from optimization, algebraic geometry, logic and model theory, discrete complexity theory and engineering.

Host: Peter Kornerup