6 ms·

There have been (at least semi-)serious proposals that P=NP based on the fact that nature seems to be able to find optima to NP-hard optimization problems such

There have been (at least semi-)serious proposals that P=NP based on the fact that nature seems to be able to find optima to NP-hard optimization problems such as minimizing the area:volume ratio in a foam. Of course, they have been unable to give any reasonable arguments as to why those should be global optima.

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 ago
  NP-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 ago
  Yeah 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...
jepler 6y ago
Proposals which don't survive contact with experiment. See pp. 3-4 of https://www.scottaaronson.com/papers/npcomplete.pdf https://www.scottaaronson.com/papers/npcomplete.pdf
javajosh 6y ago
It's troubling to me to talk about "nature solving problems". Nature doesn't "solve" anything, those are meanings we humans assign to the various configurations of matter that we see, guided by our understanding of the underlying principles of motion (energy, fields, forces, or however you want to express them). I mean, did nature "solve the problem" of creating human-like consciousness from inanimate matter? I suppose so, since humans are certainly human-like, and it would appear that there is a reasonable path from t=0 to now that includes building up all the structures at every scale to allow us to come enough into existence to talk about it with each other. But this way of speaking implies something that isn't there, namely an intention. Humans, to take one example, aren't a solution to a problem, we just are. And its the same for all interesting phenomena like, for example, the parabolic shape of a particle being thrown on Earth, or ball packing, or crystal lattices.... The fact that these structures are solutions to a problem is an artifact of the human ability to model the system mathematically in the first place. Nature doesn't model, she just is.
- Sharlin 6y ago
  Of course it's just a figure of speech. But it gets awkward to talk about, say, evolution, unless you can use anthropomorphic language at times. Even mathematicians discuss math using sloppy language all the time, only with the silent understanding that they could do everything rigorously if they really wanted to. Programmers anthropomorphize computers and software all the time. Does a sudoku solver not solve a problem just because it has no agency? Or is it different just because the human who wrote it does?
  - javajosh 6y ago
    I think the distinction is important to address for the current discussion about P=NP, because of the meta nature of the discussion. Any argument about natural phenomena meaning anything a priori is obscuring the computation required ot assert meaning.
SilasX 6y ago
Shameless plug for my Hiter parody of cranks who write such papers (modeled after Scott Aaronson's reaction to such a paper [0]). https://www.youtube.com/watch?v=NwUQVv7wCGA https://www.youtube.com/watch?v=NwUQVv7wCGA [0] https://www.scottaaronson.com/papers/npcomplete.pdf https://www.scottaaronson.com/papers/npcomplete.pdf >> Last summer Bringsjord and Taylor posted a paper entitled “P=NP” to the arXiv. This paper argues that, since (1) finding a Steiner tree is NP-hard, (2) soap bubbles find a Steiner tree in polynomial time, (3) soap bubbles are classical objects, and (4) classical physics can be simulated by a Turing machine with polynomial slowdown, it follows that P=NP. >> My immediate reaction was that the paper was a parody.
- Sharlin 6y ago
  Yeah, that rebuttal paper of Scott's was what I had in mind as well. And that Hitler parody was surprisingly funny, thanks :D
  - SilasX 6y ago
    Glad to hear!
- gonzo 6y ago
  Funny. Thanks!
- mikhailfranco 6y ago
  ... visions of the NSA buying lots of washing-up liquid and old wire coat hangers.
LolWolf 6y ago
Yeah, for sure. I mean, it's often the case (as I've found in my own research) that even relatively unsophisticated heuristics will often nail the global optimum for a good number of problems. Here's one particular example: I tried what is essentially a greedy heuristic on a physical design problem (a problem where we design a device such that an excited wave within it best matches a specific shape). I had earlier showed that solving the general problem is NP-hard. The objective value the greedy heuristic returned? .589. It took <100ms to compute this. Now, I rewrote the problem in a way that was amenable to a mixed-integer convex problem solver (which involved some somewhat-complicated reductions because the problem isn't easily phrased in this way). Put it on Mosek (which is a pretty fast solver) and let it run. The globally-certified optimal value (to <1%)? .587. Mosek took two and a half hours to find this. So, tl;dr, the problem was "hard enough" that a branch-and-bound solver took a long time to solve, but still "easy enough" that a basic heuristic might as well have nailed the global optimum. ----- I think the reason such papers keep popping up (and I see them around surprisingly often) is that people really don't realize how good basic heuristics really can be!

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 ago
NP-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 ago
Yeah 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...

jepler 6y ago

Proposals which don't survive contact with experiment. See pp. 3-4 of https://www.scottaaronson.com/papers/npcomplete.pdf https://www.scottaaronson.com/papers/npcomplete.pdf

javajosh 6y ago

It's troubling to me to talk about "nature solving problems". Nature doesn't "solve" anything, those are meanings we humans assign to the various configurations of matter that we see, guided by our understanding of the underlying principles of motion (energy, fields, forces, or however you want to express them). I mean, did nature "solve the problem" of creating human-like consciousness from inanimate matter? I suppose so, since humans are certainly human-like, and it would appear that there is a reasonable path from t=0 to now that includes building up all the structures at every scale to allow us to come enough into existence to talk about it with each other. But this way of speaking implies something that isn't there, namely an intention. Humans, to take one example, aren't a solution to a problem, we just are. And its the same for all interesting phenomena like, for example, the parabolic shape of a particle being thrown on Earth, or ball packing, or crystal lattices.... The fact that these structures are solutions to a problem is an artifact of the human ability to model the system mathematically in the first place. Nature doesn't model, she just is.

Sharlin 6y ago
Of course it's just a figure of speech. But it gets awkward to talk about, say, evolution, unless you can use anthropomorphic language at times. Even mathematicians discuss math using sloppy language all the time, only with the silent understanding that they could do everything rigorously if they really wanted to. Programmers anthropomorphize computers and software all the time. Does a sudoku solver not solve a problem just because it has no agency? Or is it different just because the human who wrote it does?
- javajosh 6y ago
  I think the distinction is important to address for the current discussion about P=NP, because of the meta nature of the discussion. Any argument about natural phenomena meaning anything a priori is obscuring the computation required ot assert meaning.

SilasX 6y ago

Shameless plug for my Hiter parody of cranks who write such papers (modeled after Scott Aaronson's reaction to such a paper [0]). https://www.youtube.com/watch?v=NwUQVv7wCGA https://www.youtube.com/watch?v=NwUQVv7wCGA [0] https://www.scottaaronson.com/papers/npcomplete.pdf https://www.scottaaronson.com/papers/npcomplete.pdf >> Last summer Bringsjord and Taylor posted a paper entitled “P=NP” to the arXiv. This paper argues that, since (1) finding a Steiner tree is NP-hard, (2) soap bubbles find a Steiner tree in polynomial time, (3) soap bubbles are classical objects, and (4) classical physics can be simulated by a Turing machine with polynomial slowdown, it follows that P=NP. >> My immediate reaction was that the paper was a parody.

Sharlin 6y ago
Yeah, that rebuttal paper of Scott's was what I had in mind as well. And that Hitler parody was surprisingly funny, thanks :D
- SilasX 6y ago
  Glad to hear!
gonzo 6y ago
Funny. Thanks!
mikhailfranco 6y ago
... visions of the NSA buying lots of washing-up liquid and old wire coat hangers.

LolWolf 6y ago

Yeah, for sure. I mean, it's often the case (as I've found in my own research) that even relatively unsophisticated heuristics will often nail the global optimum for a good number of problems. Here's one particular example: I tried what is essentially a greedy heuristic on a physical design problem (a problem where we design a device such that an excited wave within it best matches a specific shape). I had earlier showed that solving the general problem is NP-hard. The objective value the greedy heuristic returned? .589. It took <100ms to compute this. Now, I rewrote the problem in a way that was amenable to a mixed-integer convex problem solver (which involved some somewhat-complicated reductions because the problem isn't easily phrased in this way). Put it on Mosek (which is a pretty fast solver) and let it run. The globally-certified optimal value (to <1%)? .587. Mosek took two and a half hours to find this. So, tl;dr, the problem was "hard enough" that a branch-and-bound solver took a long time to solve, but still "easy enough" that a basic heuristic might as well have nailed the global optimum. ----- I think the reason such papers keep popping up (and I see them around surprisingly often) is that people really don't realize how good basic heuristics really can be!