LENORE BLUM
Distinguished Career Professor, Computer Science
www

Complexity and Real Computation. In 1989, Steve Smale, Mike Shub and I introduced a theory of computation and complexity over an arbitrary ring or field R. In 1997, along with Felipe Cucker, we published a book, Complexity and Real Computation (Springer-Verlag). From our Introduction: "The classical theory of computation had its origin in the work of logicians -- of Godel, Turing, ... , among others -- in the 1930's. The model of computation developed in the following decades, the Turing machine, has been extraordinarily successful in giving the foundations and framework for theoretical computer science.

"The point of view of this book is that the Turing model (we call it "classical") with it's dependence on 0's and 1's, is fundamentally inadequate for giving such a foundation for modern scientific computation, where most of the algorithms - with origins in Newton, Euler, Gauss, et al. - are real number algorithms."

Our approach applies to the analysis of algorithms over continuous domains as well as the discrete. The classical theory is recovered if we allow the ring R to be Z_2 (the integers mod 2). But now R can also be the real or complex numbers, or any other field. The familiar complexity classes P, NP and fundamental question "does P= NP?" make sense over R and moreover, relate explicitly to fundamental problems in mathematics such as Hilbert's Nullstellensatz. Thus, we are particularly interested in research concerning the complexity of algorithms that solve systems of polynomial equations.

Transfer Principles for Complexity Theory. A powerful tool of the classical theory is that of reduction: If problem A can be shown to be reducible to problem B, then techniques for solving B can be used to solve A. Classically, A and B are both discrete, i.e. defined over the same domain Z_2. But now we have an additional powerful tool, namely that of transfer: When there was essentially only one model of computation (i.e. over Z_2), it didn't make sense to transfer complexity results from one domain to another. But now, transfer becomes a real possibility. We can ask: Suppose we can show P=NP over the complex numbers (using all the mathematics that is natural here). Then can we conclude that P=NP over another field such as the algebraic numbers or even over Z_2? (Answer: Yes and essentially yes.)

I am particularly interested in such transfer results and problems that appear in the interface between the discrete and the continuous.