https://royalsocietypublishing.org/doi/10.1098/rsos.180396Abstract
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 traveling 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.
Good comparison.jedishrfu said:The difference between computationally finding a geodesic vs actually letting gravity do its thing.
I think I've read something similar. On the other hand, IIRC (it's really long ago) then NP problems are solvable in P if there is an oracle tape attached to the TM. The scents can probably be interpreted as such a tape.anorlunda said:Weren't there earlier reports of the traveling salesmen solved by bees or ants? I recall that they left scent trails, shortest paths had the strongest scent, and later ants followed the strongest scent.
An NP problem, or non-deterministic polynomial time problem, is a type of computational problem that is difficult to solve using traditional algorithms. These problems require a large amount of time and resources to solve, and their complexity increases as the problem size grows.
An amoeba is often used as a metaphor to explain the concept of an NP problem. Just as an amoeba can quickly grow and multiply, an NP problem can quickly become very complex and difficult to solve as the problem size increases.
No, an amoeba has not actually solved an NP problem. The use of an amoeba as a metaphor for NP problems is simply to illustrate the concept of a problem that grows exponentially in complexity.
Yes, there have been recent developments in using biological systems, including amoebas, to help solve NP problems. This branch of research is known as biological computing and has shown promising results in solving complex problems more efficiently.
No, not all NP problems can be solved using amoebas or other biological systems. These methods are still in the early stages of research and may not be applicable to all types of NP problems. Traditional computing methods are still necessary for many types of NP problems.