Science Alert December 21, 2018
An international team of researchers (China, Japan) used a unicellular plasmodium of Physarum polycephalum to search for a solution to the travelling salesman problem (TSP) by changing its shape to minimize the risk of being exposed to aversive light stimuli. They found 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. The quality of the solution does not degrade despite the explosive expansion of the search space. They formulated a computational model to 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… read more. Open Access TECHNICAL ARTICLE
Unrelated linear vs exponential graph (Luo, Researchgate)