Ebook: Complexity and Real Computation

Computational complexity theory provides a framework for understanding the cost of solving computational problems, as measured by the requirement for resources such as time and space. The objects of study are algorithms defined within a formal model of computation. Upper bounds on the computational complexity of a problem are usually derived by constructing and analyzing specific algorithms. Meaningful lower bounds on computational complexity are harder to come by, and are not available for most problems of interest. The dominant approach in complexity theory is to consider algorithms as oper­ ating on finite strings of symbols from a finite alphabet. Such strings may represent various discrete objects such as integers or algebraic expressions, but cannot rep­ resent real or complex numbers, unless the numbers are rounded to approximate values from a discrete set. A major concern of the theory is the number of com­ putation steps required to solve a problem, as a function of the length of the input string.

---

The classical theory of computation has its origins in the work of Goedel, Turing, Church, and Kleene and has been an extraordinarily successful framework for theoretical computer science. The thesis of this book, however, is that it provides an inadequate foundation for modern scientific computation where most of the algorithms are real number algorithms. The goal of this book is to develop a formal theory of computation which integrates major themes of the classical theory and which is more directly applicable to problems in mathematics, numerical analysis, and scientific computing. Along the way, the authors consider such fundamental problems as: * Is the Mandelbrot set decidable? * For simple quadratic maps, is the Julia set a halting set? * What is the real complexity of Newton's method? * Is there an algorithm for deciding the knapsack problem in a ploynomial number of steps? * Is the Hilbert Nullstellensatz intractable? * Is the problem of locating a real zero of a degree four polynomial intractable? * Is linear programming tractable over the reals? The book is divided into three parts: The first part provides an extensive introduction and then proves the fundamental NP-completeness theorems of Cook-Karp and their extensions to more general number fields as the real and complex numbers. The later parts of the book develop a formal theory of computation which integrates major themes of the classical theory and which is more directly applicable to problems in mathematics, numerical analysis, and scientific computing.

---

The classical theory of computation has its origins in the work of Goedel, Turing, Church, and Kleene and has been an extraordinarily successful framework for theoretical computer science. The thesis of this book, however, is that it provides an inadequate foundation for modern scientific computation where most of the algorithms are real number algorithms. The goal of this book is to develop a formal theory of computation which integrates major themes of the classical theory and which is more directly applicable to problems in mathematics, numerical analysis, and scientific computing. Along the way, the authors consider such fundamental problems as: * Is the Mandelbrot set decidable? * For simple quadratic maps, is the Julia set a halting set? * What is the real complexity of Newton's method? * Is there an algorithm for deciding the knapsack problem in a ploynomial number of steps? * Is the Hilbert Nullstellensatz intractable? * Is the problem of locating a real zero of a degree four polynomial intractable? * Is linear programming tractable over the reals? The book is divided into three parts: The first part provides an extensive introduction and then proves the fundamental NP-completeness theorems of Cook-Karp and their extensions to more general number fields as the real and complex numbers. The later parts of the book develop a formal theory of computation which integrates major themes of the classical theory and which is more directly applicable to problems in mathematics, numerical analysis, and scientific computing.
Content:
Front Matter....Pages i-xvi
Front Matter....Pages 1-1
Introduction....Pages 3-36
Definitions and First Properties of Computation....Pages 37-68
Computation over a Ring....Pages 69-81
Decision Problems and Complexity over a Ring....Pages 83-98
The Class NP and NP-Complete Problems....Pages 99-112
Integer Machines....Pages 113-124
Algebraic Settings for the Problem “P ? NP?”....Pages 125-146
Back Matter....Pages 147-149
Front Matter....Pages 151-151
Newton’s Method....Pages 153-168
Fundamental Theorem of Algebra: Complexity Aspects....Pages 169-186
B?zout’s Theorem....Pages 187-200
Condition Numbers and the Loss of Precision of Linear Equations....Pages 201-215
The Condition Number for Nonlinear Problems....Pages 217-236
Complexity and the Condition Number....Pages 237-259
Linear Programming....Pages 261-273
Back Matter....Pages 275-296
Front Matter....Pages 297-299
Deterministic Lower Bounds....Pages 301-301
Probabilistic Machines....Pages 303-315
Parallel Computations....Pages 317-334
Some Separations of Complexity Classes....Pages 335-357
Weak Machines....Pages 359-375
Front Matter....Pages 377-384
Additive Machines....Pages 301-301
Nonuniform Complexity Classes....Pages 385-400
Descriptive Complexity....Pages 401-409
Back Matter....Pages 411-429
....Pages 431-453