Computing over the Reals: Where Turing Meets Newton

posted Jul 9, 2010, 10:26 AM by Glenna Buford

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 Z2 = {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 Z2, 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 Z2? (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.