Complexity and real computation
by Lenore Blum · first published 1998
4mentions
2recommended by
2HN commenters
2017–2022first – last mentioned
100% recommend
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 th
Affiliate links. As an Amazon Associate I earn from qualifying purchases.
Look into work of Lenora Blum. She wrote a book "Complexity and Real computation".
on “Analog Computers” ↗The extended Turing-Church thesis states that an analog computer can be simulated on a Turing machine. It can but not efficiently. Look into the work of Lenora Blum. She wrote a book "Complexity and Real computation".
on “Analog Computers” ↗…it doesn't apply to the Turing machine model which is what most people think of when they hear of P vs NP. There is a wonderful and mathematically accessible book from the 1990s about the BSS model: Complexity and Real Computation, by Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale. I thought it was going to open up into a big field, but I don't know if much happened with it. See also: https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smal...
on “Poly-time algorithm for deciding Hilbert Nullstellensatz. A proof of P=NP” ↗…Especially given that most uses of the continuous variable systems is to encode discrete qubits Current uses, maybe. > Is there any Complexity Theory work published about continuous variable models? "Complexity and Real Computation". > And photonic systems do not magically fix the noise issue. Noise grows in a fast non-linear fashion with the size of the system, so the "constant factor" noise suppression you gain from switching…
on “The Future of Computing Is Analog” ↗