## Lenore Blum
Distinguished Career Professor of Computer Science, Carnegie Mellon University
### AWM Emmy Noether Lecture
Monday, January 7, 2002
9:00 a.m. - 9:50 a.m.
Room 6 A/B San Diego Convention Center
San Diego, California
**Abstract.** The classical *(Turing) theory of computation* has been extraordinarily successful in providing the foundations and framework for theoretical computer science. Yet its dependence on 0's and 1's is fundamentally inadequate for providing such a foundation for modern scientific computation where most algorithms - with origins in Newton, Euler, Gauss, et al. - are real number algorithms.
In 1989, Mike Shub, Steve Smale and I introduced a theory of computation and complexity over an arbitrary ring or field R. If R is Z^{2} = {0,1}, the classical computer science theory is recovered. If R is the field of real numbers, *Newton's algorithm*, the paradigm algorithm of numerical analysis, fits naturally into our model of computation.
*Complexity classes* P, NP and the *fundamental question* "Does P= NP?" can be formulated naturally over an arbitrary ring R. The answer to the fundamental question depends on the complexity of deciding feasibility of polynomial systems over R. When R is Z^{2}, this becomes the classical *satisfiability* problem of Cook-Karp-Levin. When R is the field of complex numbers, the answer depends on the complexity of *Hilbert's Nullstellensatz*.
The notion of *reduction* between problems (e.g. between *traveling salesman* and *satisfiability* ) has been a powerful tool in classical complexity theory. But now, in addition, the *transfer of complexity* results from one domain to another becomes a real possibility. For example, 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.)
In this talk, I will discuss these results and indicate how basic notions from numerical analysis such as *condition*, round off and approximation are being introduced into complexity theory, bringing together ideas germinating from the real calculus of Newton and the discrete computation of computer science. |