I realized this when it turns out that ants can solve a similar NP problem linearly or nearly P when it comes to setting up their tracks.
LC On Saturday, December 22, 2018 at 8:09:39 PM UTC-6, Brent wrote: > > Bruno should enjoy this. > > Brent > > > -------- Forwarded Message -------- > > This is a cool bio hack, but is this approach ever going to be faster > and/or cheaper than an electronic computer for the same precision of > optimization? > > > https://phys.org/news/2018-12-amoeba-approximate-solutions-np-hard-problem.html > > > Amoeba finds approximate solutions to NP-hard problem in linear time > > December 20, 2018 by Lisa Zyga, Phys.org > > Researchers have demonstrated that an amoeba--a single-celled organism > consisting mostly of gelatinous protoplasm--has unique computing > abilities that may one day offer a competitive alternative to the > methods used by conventional computers. > > The researchers, led by Masashi Aono at Keio University, assigned an > amoeba to solve the Traveling Salesman Problem (TSP). The TSP is an > optimization problem in which the goal is to find the shortest route > between several cities, so that each city is visited exactly once, and > the start and end points are the same. > > https://royalsocietypublishing.org/doi/pdf/10.1098/rsos.180396 > > Remarkable problem-solving ability of unicellular amoeboid organism > and its mechanism > > Choosing a better move correctly and quickly is a fundamental skill of > living organisms that corresponds to solving a computationally > demanding problem. A unicellular plasmodium of Physarum polycephalum > searches for a solution to the travelling salesman problem (TSP) by > changing its shape to minimize the risk of being exposed to aversive > light stimuli. In our previous studies, we reported the results on > the eight-city TSP solution. In this study, we show that the time > taken by plasmodium to find a reasonably high-quality TSP solution > grows linearly as the problem size increases from four to eight. > Interestingly, the quality of the solution does not degrade despite > the explosive expansion of the search space. Formulating a > computational model, we show that the linear-time solution can be > achieved if the intrinsic dynamics could allocate intracellular > resources to grow the plasmodium terminals with a constant rate, even > while responding to the stimuli. These results may lead to the > development of novel analogue computers enabling approximate solutions > of complex optimization problems in linear time. > > > -- 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.
