On Wed, Oct 1, 2014 at 9:18 AM, Bruno Marchal <marc...@ulb.ac.be> wrote:
> As I've said no natural phenomenon has ever been found where nature must >> solve a NP-hard problem >> > > > To solve it exactly? > Obviously exactly. > swarm of ants solves efficaciously NP complete problem, like the > traveling salesman problem. > It's not hard to find a pretty good solution to the traveling salesman problem, but it's next to impossible to find the perfect one unless the number of cities is very small, impossible for us, for our computers, for ants, and for nature in general. > I think some soap film solves some NP problem too, > No they do not. As I pointed out before if you assume that soap films make use of Real Numbers then yes, soap films can solve a NP problem, but when the experimental is actually performed it fails to even come close to doing so. I'll now repeat what I said before. Scott Aaronson actually tried it and this is what he reports: "Taking two glass plates with pegs between them, and dipping the resulting contraption into a tub of soapy water. The idea is that the soap bubbles that form between the pegs should trace out the minimum Steiner tree — that is, the minimum total length of line segments connecting the pegs, where the segments can meet at points other than the pegs themselves. Now, this is known to be an NP-hard optimization problem. So, it looks like Nature is solving NP-hard problems in polynomial time! Long story short, I went to the hardware store, bought some glass plates, liquid soap, etc., and found that, while Nature does often find a minimum Steiner tree with 4 or 5 pegs, it tends to get stuck at local optima with larger numbers of pegs. Indeed, often the soap bubbles settle down to a configuration which is not even a tree (i.e. contains “cycles of soap”), and thus provably can’t be optimal. The situation is similar for protein folding. Again, people have said that Nature seems to be solving an NP-hard optimization problem in every cell of your body, by letting the proteins fold into their minimum-energy configurations. But there are two problems with this claim. The first problem is that proteins, just like soap bubbles, sometimes get stuck in suboptimal configurations — indeed, it’s believed that’s exactly what happens with Mad Cow Disease. The second problem is that, to the extent that proteins do usually fold into their optimal configurations, there’s an obvious reason why they would: natural selection! If there were a protein that could only be folded by proving the Riemann Hypothesis, the gene that coded for it would quickly get weeded out of the gene pool." By the way I just finished reading Scott Aaronson's book "Quantum Computing since Democritus" and it's excellent. John K Clark -- You received this message because you are subscribed to the Google Groups "Everything List" group. To unsubscribe from this group and stop receiving emails from it, send an email to everything-list+unsubscr...@googlegroups.com. To post to this group, send email to everything-list@googlegroups.com. Visit this group at http://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.
