4 ms·
Doesn't that line of argument only work if nature's algorithms can be shown to be both precise (giving exact solutions) and complete (able to solve every valid
by MaxBarraclough 6y ago
Doesn't that line of argument only work if nature's algorithms can be shown to be both precise (giving exact solutions) and complete (able to solve every valid problem)?
- qsort 6y agoNP-complete problems can be polynomially reduced to each other. If you had a magical oracle that was able to solve any one specific NP-complete problem in O(1) time, you could turn that into a O(n^k) solution for all NP-complete problems. That's the idea behind DNA-computing, for instance. The question is whether it is actually possible to do so at a reasonable cost and at scale. Regardless, what "nature" does has 0 to do with P vs NP, computability or anything else. P vs NP is a statement strictly about mathematical objects, there is no notion of "nature" anywhere in it.
- est31 6y agoYeah I doubt that nature is able to solve problems above a certain size. After you put together a certain number of soap bubbles they'll collapse into a black hole. Furthermore there are concerns of speed of light or speed of sound. Nature might give efficient solvers for specific problems up to a certain size, but we already have "practical" NP problem solvers in classical silicon in the form of SMT solvers.
- MaxBarraclough 6y ago> we already have "practical" NP problem solvers in classical silicon in the form of SMT solvers. They're out there, and practical for some problems, but SMT solvers aren't exactly a solved problem. They're used for deductive proofs about program correctness, which are still pretty finicky. [0] [0] https://blog.adacore.com/using-spark-to-prove-255-bit-integer-arithmetic-from-curve25519 https://blog.adacore.com/using-spark-to-prove-255-bit-intege...