Computing over the Reals: Where Turing Meets Newton
Lenore Blum · 2004
The classical (Turing) theory of computation has been extraordinarily successful in providing the foundations and framework for theoretical computer science. Yet its dependence on 0s and 1s is fundamentally inadequate for providing such a foundation for modern scientific computation, in which 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 [BSS89]. If R is Z2 = ({0, 1},+,·), the classical computer science theory is recovered. If R is the field of real numbers R, 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 in general on the complexity of deciding feasibility of polynomial systems over R. When R is Z2, this becomes the classical satisfiability problem of Cook–Levin [Cook71, Levin73]. When R is the field of complex numbers C, the answer depends on the complexity of Hilbert’s Nullstellensatz. The notion of reduction between problems (e.g., between traveling salesman and satisfiability) has