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 everything-list+unsubscr...@googlegroups.com. To post to this group, send email to firstname.lastname@example.org. Visit this group at https://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.