DeepRead
Cover of Complexity and real computation

Complexity and real computation

Lenore Blum · 1998

Minds, machines and the future › Information theory and chaos

#11,603 most recommended

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

02420172018202020222017 peak · 2
This bookAverage book in Information theory and chaos

In the commenters’ own words

What Open Library readers say

No Open Library reader has rated it yet.

  • 0 want to read
  • 1 reading
  • 0 have read

Open Library’s page for the book

What Wikipedia says

  • published 1998
  • 83 views a month

Read the Wikipedia article

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

Explore in the mosaic

Read next: its neighbours on the mosaic