
Complexity and real computation
Lenore Blum · 1998
Minds, machines and the future › Information theory and chaos
#11,603 most recommended
Hacker News
4
mentions by 2 people · top 54% of 15,732 books
Open Library
—
No ratings yet
Wikipedia
83
article views a month
About the book
The book develops a formal theory of computation over the real and complex numbers, using machine models in which arithmetic on real numbers is a primitive operation. It connects this theory to classical complexity theory, including the NP-completeness results of Cook and Karp, and extends them to these number fields. Its scope covers mathematics, numerical analysis, and scientific computing. The classical Turing-based theory of computation, built on the work of Gödel, Turing, Church, and Kleene, is presented as an inadequate foundation for scientific computation, because most practical algorithms operate on real numbers rather than bits. The authors argue that a theory of computation over the reals can be built on the same footing as the classical one and yields its own notions of decidability, complexity, and NP-completeness. They apply this framework to questions such as whether the Mandelbrot set is decidable, the complexity of Newton's method, and the tractability of linear programming and of finding real zeros of polynomials.
Written by Claude from what it knows of this book.
What Hacker News says 100% recommend · 0% critical
In the commenters’ own words
My first thought from the title was that this result is in the Blum-Shub-Smale computational model rather than the traditional Turing machine model. In the…
> Especially given that most uses of the continuous variable systems is to encode discrete qubits Current uses, maybe. > Is there any Complexity Theory work…
What Open Library readers say
No Open Library reader has rated it yet.
- 0 want to read
- 1 reading
- 0 have read
What Wikipedia says
- published 1998
- 83 views a month
Reddit communities — coming later
Details
- First published
- 1998
- ISBN
- 9780387982816
- Editions known
- 8 at Open Library
- Open Library
- OL17773285W
AlgorithmesComplexité de calcul (Informatique)Computational complexityComputer algorithmsComputer scienceInformation theoryInformatiqueMathematical Logic and FoundationsMathematicsMathematics, data processingReal-time data processingSymbolic and mathematical LogicTemps réel (Informatique)Theory of Computation
Read next: its neighbours on the mosaic
Markov LogicDaniel Lowd · 2009 · recommended by 1 person · loosely similar by subject
A course in number theory and cryptographyNeal Koblitz · 1987 · recommended by 1 person · loosely similar by subject
The nature of computationCristopher Moore · 2009 · recommended by 10 people · similar by subject and what people say about it
ComputationMarvin Minsky · 1967 · recommended by 5 people · similar by subject and what people say about it
Theory of computationMichael Sipser · 2007 · recommended by 14 people · similar by subject and what people say about it
Computational complexitySanjeev Arora · 2007 · recommended by 3 people · similar by subject and what people say about it
Introduction to the theory of computationMichael Sipser · 1997 · recommended by 66 people · similar by subject and what people say about it
Computability and complexityNeil D. Jones · 1997 · recommended by 1 person · similar by subject and what people say about it
Computability and logicGeorge Boolos · 1974 · recommended by 7 people · similar by subject and what people say about it
The Computational Beauty of NatureGary William Flake · 1998 · recommended by 19 people · similar by subject and what people say about it
Stack computersPhilip Koopman · 1989 · recommended by 9 people · loosely similar by subject
Computational complexityChristos H. Papadimitriou · 1994 · recommended by 7 people · similar by subject and what people say about it
Quantum Computing Since DemocritusScott Aaronson · 2013 · recommended by 73 people · similar by subject and what people say about it
Quantum computation and quantum informationMichael A. Nielsen · 2000 · recommended by 30 people · similar by subject and what people say about it
Computers and intractabilityMichael R. Garey · 1979 · recommended by 5 people · similar by subject and what people say about it
A mathematical introduction to logicHerbert B. Enderton · 1972 · recommended by 6 people · loosely similar by subject
Introduction to ProbabilityJoseph K. Blitzstein · 2014 · recommended by 5 people · loosely similar by subject
Introduction to automata theory, languages, and computationJohn E. Hopcroft · 1979 · recommended by 24 people · similar by subject and what people say about it
Understanding ComputationTom Stuart · 2013 · recommended by 13 people · similar by subject and what people say about it
Computation structuresStephen A. Ward · 1990 · recommended by 8 people · similar by subject and what people say about it
Feynman lectures on computationRichard Phillips Feynman · 1996 · recommended by 17 people · similar by subject and what people say about it
Quantum Computer ScienceN. David Mermin · 2007 · recommended by 11 people · similar by subject and what people say about it
Basic category theory for computer scientistsBenjamin C. Pierce · 1991 · recommended by 12 people · loosely similar by subject
Practical Foundations for Programming LanguagesRobert Harper · 2016 · recommended by 17 people · similar by subject and what people say about it