AN INTRODUCTION TO REAL NUMBER COMPLEXITY THEORY
Dr Klaus Meer, RWTH Aachen, Germany

Abstract: 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 for a long time in algebraic complexity theory, where the complexity of problems in a fixed real space Rn are 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.

In this survey talk we want to outline the basic ideas of that approach. In particular we'll discuss:

* the existence of complete problems in the BSS setting
* the (real number) complexity of mathematical optimization problems
* transfer theorems for the P versus NP question and relations between real number and discrete complexity theory
* descriptive complexity over the reals

This seminar was held at the Department of Computer Science, Royal Holloway, University of London on 20 July 1999.

back