Complexity and real computation
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.
Stats for nerds
2recommend
4mentions
2people
2017–2022years
100% recommend
Mentions per year
What Hacker News says
- 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 BSS model, arithmetic operations on exact real numbers are done in constant time. That is useful for analyzing numerical algorithms where you are more interested in e.g. convergence speed than things like roundoff errors. But the exact real arithmetic in constant time is equivalent to doing infinite-precision integer arithmetic in constant time. A couple of people already have mentioned the latter as an assumption of the paper as if that were a big error, but in the BSS model it is part of the deal. Thus the BSS model gives speedups for some problem classes and it's not a big surprise that P=NP there.
I didn't realize P vs NP was supposed to be an open problem in the BSS model. I thught that this solution was an early result. The catch is simply that 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...
- > 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 to photonic systems is quickly washed away.
Is there anything published on the fact that this cannot be overcome?
- Look into work of Lenora Blum. She wrote a book "Complexity and Real computation".
- 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".
Related
Computational complexity
7 recommend · 9
Introduction to the theory of computation
66 recommend · 96
Theory of computation
14 recommend · 21
Introduction to Algorithms
274 recommend · 880
Think Complexity
11 recommend · 19
A new kind of science
44 recommend · 388
