''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 Sir Roger Penrose (born 8 August 1931) is an English mathematician, mathematical physicist, philosopher of science and Nobel Laureate in Physics. He is Emeritus Rouse Ball Professor of Mathematics in the University of Oxford, an emeritus fello ...

in '' The Emperor's New Mind'': "is the Mandelbrot set computable?" The book was written by Lenore Blum,

Felipe Cucker Juan Felipe Cucker Farkas (born 1958) is an Uruguayan mathematician and theoretical computer scientist who has done research into the complexity theory of the Blum–Shub–Smale computational model and the complexity of numerical algorithms ...

, Michael Shub and

Stephen Smale Stephen Smale (born July 15, 1930) is an American mathematician, known for his research in topology, dynamical systems and mathematical economics. He was awarded the Fields Medal in 1966 and spent more than three decades on the mathematics facult ...

, with a foreword by

Richard M. Karp Richard Manning Karp (born January 3, 1935) is an American computer scientist and computational theorist at the University of California, Berkeley. He is most notable for his research in the theory of algorithms, for which he received a Turing ...

, and published by Springer-Verlag in 1998 ( doi:10.1007/978-1-4612-0701-6, ).

Purpose

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.

Topics

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 Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems ar ...

, 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 field In mathematics, a field is algebraically closed if every non-constant polynomial in (the univariate polynomial ring with coefficients in ) has a root in . Examples As an example, the field of real numbers is not algebraically closed, because ...

s 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 Eric Bach is an American computer scientist who has made contributions to computational number theory. Bach completed his undergraduate studies at the University of Michigan, Ann Arbor, and got his Ph.D. in computer science from the University o ...

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 In numerical analysis, Newton's method, also known as the Newton–Raphson method, named after Isaac Newton and Joseph Raphson, is a root-finding algorithm which produces successively better approximations to the roots (or zeroes) of a real-valu ...

for these algorithms, and on author Stephen Smale's alpha theory for

numerical certification Numerical certification is the process of verifying the correctness of a candidate solution to a system of equations. In (numerical) computational mathematics, such as numerical algebraic geometry, candidate solutions are computed algorithmically, ...

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 In numerical analysis, the condition number of a function measures how much the output value of the function can change for a small change in the input argument. This is used to measure how sensitive a function is to changes or errors in the input ...

of systems of equations, and the time complexity of

linear programming Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear function#As a polynomial function, li ...

with rational coefficients. Part III provides analogues of

structural complexity theory In computational complexity theory of computer science, the structural complexity theory or simply structural complexity is the study of complexity classes, rather than computational complexity of individual problems and algorithms. It involves t ...

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.

Audience and reception

The book is aimed at the level of a graduate student or researcher in these topics, and in places it assumes background knowledge of classical computational complexity theory,

differential geometry Differential geometry is a mathematical discipline that studies the geometry of smooth shapes and smooth spaces, otherwise known as smooth manifolds. It uses the techniques of differential calculus, integral calculus, linear algebra and multili ...

, topology, and dynamical systems. Reviewer Klaus Meer writes that the book is "very well written", "perfect to use on a graduate level", and well-represents both the state of the art in this area and the strong connections that can be made between fields as diverse as

algebraic number theory Algebraic number theory is a branch of number theory that uses the techniques of abstract algebra to study the integers, rational numbers, and their generalizations. Number-theoretic questions are expressed in terms of properties of algebraic ob ...

algebraic geometry Algebraic geometry is a branch of mathematics, classically studying zeros of multivariate polynomials. Modern algebraic geometry is based on the use of abstract algebraic techniques, mainly from commutative algebra, for solving geometrical ...

, mathematical logic, and numerical analysis. As a minor criticism, aimed more at the Blum–Shub–Smale model than the book, Stephen Vavasis observes that (unlike with Turing machines) seemingly-minor details in the model, such as the ability to compute the floor and ceiling functions, can make big differences in what is computable and how efficiently it can be computed. However, Vavasis writes, "this difficulty is probably inherent in the topic". Relatedly,

complains that assigning unit cost to all arithmetic operations can give a misleading idea of a problem's complexity in practical computation, and Vavasis also notes that, as of the publication date of his review, this work had seemingly had little effect on practical research in scientific computing. Despite these issues, he recommends the book as a convenient and clearly-written compendium of the theory of numerical computing.

References

{{reflist, refs= {{citation, title=Review of ''Complexity and Real Computation'', journal=

Mathematical Reviews ''Mathematical Reviews'' is a journal published by the American Mathematical Society (AMS) that contains brief synopses, and in some cases evaluations, of many articles in mathematics, statistics, and theoretical computer science. The AMS also pu ...

, first=Klaus, last=Meer, year=1999, mr=1479636 {{citation, last=Vavasis, first=Stephen A., date=June 1999, jstor=2653097, pages=407–409, journal= SIAM Review, volume=41, issue=2, title=Review of ''Complexity and Real Computation'' {{citation, last=Bach, first=Eric, author-link=Eric Bach, pages=145–146, journal=Discrete Dynamics in Nature and Society, volume=6, year=2001, title=Review of ''Complexity and Real Computation'', doi=10.1155/S1026022601000152, doi-access=free {{citation, last=McNicholl, first=Timothy H., date=June 2001, doi=10.1145/504192.1005765, issue=2, journal= SIGACT News, pages=14–15, title=Review of ''Complexity and Real Computation'', volume=32

External links

''Complexity and Real Computation''
at the Internet Archive Models of computation Computational complexity theory Mathematics books 1998 non-fiction books