Complexity and Real Computation is a book on the computational complexity theory of real computation. It studies algorithms whose inputs and outputs are real numbers, using the Blum–Shub–Smale machine as its model of computation. For instance, this theory is capable of addressing a question posed in 1991 by Roger Penrose in The Emperor’s New Mind: “is the Mandelbrot set computable?”
Stephen Vavasis observes that this book fills a significant gap in the literature: although theoretical computer scientists working on discrete algorithms had been studying models of computation and their implications for the complexity of algorithms since the 1970s, researchers in numerical algorithms had for the most part failed to define their model of computation, leaving their results on a shaky foundation. Beyond the goal of making this aspect of the topic more well-founded, the book also has the aims of presenting new results in the complexity theory of real-number computation, and of collecting previously-known results in this theory.
The introduction of the book reprints the paper “Complexity and real computation: a manifesto”, previously published by the same authors. This manifesto explains why classical discrete models of computation such as the Turing machine are inadequate for the study of numerical problems in areas such as scientific computing and computational geometry, motivating the newer model studied in the book. Following this, the book is divided into three parts.
Part I of the book sets up models of computation over any ring, with unit cost per ring operation. It provides analogues of recursion theory and of the P versus NP problem in each case, and proves the existence of NP-complete problems analogously to the proof of the Cook–Levin theorem in the classical model, which can be seen as the special case of this theory for modulo-2 arithmetic. The ring of integers is studied as a particular example, as are the algebraically closed fields of characteristic zero, which are shown from the point of view of NP-completeness within their computational models to all be equivalent to the complex numbers. (Eric Bach points out that this equivalence can be seen as a form of the Lefschetz principle.)
Part II focuses on numerical approximation algorithms, on the use of Newton’s method for these algorithms, and on author Stephen Smale’s alpha theory for numerical certification of the accuracy of the results of these computations. Other topics considered in this section include finding the roots of polynomials and the intersection points of algebraic curves, the condition number of systems of equations, and the time complexity of linear programming with rational coefficients.
Part III provides analogues of structural complexity theory and descriptive complexity theory for real-number computation, including many separations of complexity classes that are provable in this theory even though the analogous separations in classical complexity theory remain unproven. A key tool in this area is the use of the number of connected components of a semialgebraic set to provide a lower bound on the time complexity of an associated computational problem.