Complexity and Real Computation
- ISBN-10
- 1461207010
- ISBN-13
- 9781461207016
- Category
- Computers
- Pages
- 453
- Language
- English
- Published
- 2012-12-06
- Publisher
- Springer Science & Business Media
- Authors
- Lenore Blum, Felipe Cucker, Michael Shub
Description
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.
Get the book
Other editions
Similar books
-
Complexity Theory of Real Functions
By K. KoOne of the examples is the recent work on algorithmic theory of per mutation groups. In the area of numerical computation, there are also two tradi tionally independent approaches: recursive analysis and numerical analysis.
-
Computational Complexity: A Modern Approach
By Sanjeev Arora, Boaz BarakNew and classical results in computational complexity, including interactive proofs, PCP, derandomization, and quantum computation. Ideal for graduate students.
-
Logical Foundations of Mathematics and Computational Complexity: A Gentle Introduction
By Pavel PudlákThe two main themes of this book, logic and complexity, are both essential for understanding the main problems about the foundations of mathematics.
-
Theory of Computational Complexity
By Ding-Zhu Du, Ker-I Ko... Machinery, New York, pp. 75–84. Hå stad,J.(1996), Clique is hardto approximate within , Proceedings ofthe 37thIEEE Symposiumon Foundations of Computer Science, IEEE Computer Society Press, Los Angeles, pp. 75–636. Hå stad, J.(1997) ...
-
Complexity and Approximation: In Memory of Ker-I Ko
By Jie Wang, Ding-Zhu DuKer-I also made many contributions to approximation algorithm theory of combinatorial optimization problems. This volume contains 17 contributions in the area of complexity and approximation.
-
Mathematics and Computation: A Theory Revolutionizing Technology and Science
By Avi WigdersonMathematics and Computation is useful for undergraduate and graduate students in mathematics, computer science, and related fields, as well as researchers and teachers in these fields.
-
Handbook of Computability and Complexity in Analysis
By Vasco Brattka, Peter HertlingThis handbook represents the first coherent cross-section through most active research topics on the more theoretical side of the field.
-
Complexity and Information
By J. F. Traub, A. G. WerschulzThe twin themes of computational complexity and information pervade this 1998 book.
-
Computational Complexity: A Conceptual Perspective
By Oded GoldreichThis book offers a conceptual perspective on complexity theory. It is intended to serve as an introduction for advanced undergraduate and graduate students, either as a textbook or for self-study.
-
Theory of Computation
By Dexter C. KozenThe book contains an invaluable collection of lectures for first-year graduates on the theory of computation. Topics and features include more than 40 lectures for first year graduate students, and a dozen homework sets and exercises.