Bruno should enjoy this.


-------- 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?

Amoeba finds approximate solutions to NP-hard problem in linear time

December 20, 2018 by Lisa Zyga,

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.

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 post to this group, send email to
Visit this group at
For more options, visit

Reply via email to