On Sunday, March 10, 2019 at 4:19:16 PM UTC-6, John Clark wrote: > > On Sun, Mar 10, 2019 at 5:29 PM Lawrence Crowell <[email protected] > <javascript:>> 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.* > > I read the post by Aaronson on his blog about this. It is the case that nature does find approximate solutions to NP problems in P time. The protein folding problem is another good example. The fact it is not perfect is seen with transmissible spongephore encephalies (TSEs) where polypeptides are misfolded in ways not appropriate. TSEs are running rampant in deer populations in the US, which might mean before long it is in cattle. With protein folding however the success rate is amazingly high, and where natural selections is at play. There are chaperon proteins that adjust the folding of proteins, and clearly evolution has honed in those that shape proteins in an optimal way. Again, this tends to go with the point I was making. Repeated trials and correction serve the role of closed timelike curves. Aaronson, Barvarian and Gueltrini wrote a paper [https://arxiv.org/abs/1609.05507] on how closed timelike curves that interact with a Turing machine that is not closed timelike will solve NP in P. The closed timelike curves as paths in a path integral constructive and destructively interfere to give the optimal solution. More prosaically in our time a repeated effort will approximate this in the way an ensemble can approximate a quantum system.
LC arXiv:1609.05507 <https://arxiv.org/abs/1609.05507> [pdf <https://arxiv.org/pdf/1609.05507>, ps <https://arxiv.org/ps/1609.05507>, other <https://arxiv.org/format/1609.05507>] quant-ph Computability Theory of Closed Timelike Curves Authors: Scott Aaronson <https://arxiv.org/search/quant-ph?searchtype=author&query=Aaronson%2C+S>, Mohammad Bavarian <https://arxiv.org/search/quant-ph?searchtype=author&query=Bavarian%2C+M>, Giulio Gueltrini <https://arxiv.org/search/quant-ph?searchtype=author&query=Gueltrini%2C+G> Abstract: We ask, and answer, the question of what's computable by Turing machines equipped with time travel into the past: that is, closed timelike curves or CTCs (with no bound on their size). We focus on a model for CTCs due to Deutsch, which imposes a probabilistic consistency condition to avoid grandfather paradoxes. Our main result is that computers with CTCs can solve exactly the problems that are Tu… ▽ More Submitted 18 September, 2016; originally announced September 2016. > > 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 [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.
