On Sun, Mar 10, 2019 at 5:29 PM Lawrence Crowell < goldenfieldquaterni...@gmail.com> wrote:
*> in the biological world certain problems that are NP are figured out. > This runs from ants finding the minimal distance for their trails or even > protistans negotiating some space. Ants are good at approximately solving > the traveling salesman problem, the classic NP algorithm.* It's easy to solve the traveling salesman problem if the number of cities involved is small, but I see no evidence that nature can in general solve NP problems in polynomial time. Of course there are many claims to the contrary so Quantum Computer expert Scott Aaronson decided to but the matter to a simple experimental test, this is what he reported: *"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." * > *> The ants crawl all over the place and the trails with the largest > pheremone density tend to be those that are a solution or near solution to > the traveling salesman problem.* It's not difficult to good solutions to the traveling salesman problem but it's very hard to find a the perfect solution or even to check that a proposed answer is indeed the best there is. I don't believe ants can in general find the perfect solution, but even if they did being a NP problem there is no efficient way to even check the answer, so how in the would could you know it was the perfect solution? 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 https://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.
