https://phys.org/news/2018-12-amoeba-approximate-solutions-np-hard-problem.html
This is intresting finding that
Researchers have demonstrated that an amoeba (a single-celled organism) has unique computing abilities. The researchers found that an amoeba can find reasonable (nearly optimal) solutions to the TSP in an amount of time that grows only linearly as the number of cities increases.
Traveling Salesman Problem (TSP) is an optimization problemin 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.
The problem is NP-hard, meaning that as the number of cities increases, the time needed for a computer to solve it grows exponentially.
The finding may lead to the development of novel analogue or bio-electrical computers that derive approximate solutions.
2 Comments
Tomi Engdahl says:
A Slimy, Brainless Amoeba Just Found A Completely Unexpected Solution To A College-Level Math Problem
https://www.iflscience.com/plants-and-animals/a-slimy-brainless-amoeba-just-found-a-completely-unexpected-solution-to-a-collegelevel-math-problem/
Unless you’ve studied math to a pretty high level, you probably haven’t heard of the Traveling Salesman Problem. That’s a shame because it’s one of the finest examples available to the question we’ve all asked at some point – “when will I ever need math in the real world?”
planning a journey between, say, four cities. That’s not too hard; there are only three possible routes you can take.
But if we double that number to eight cities, there are over 2,500 possible routes we can take
It’s an NP-hard problem
A new study published this week in Royal Society Open Science has shown that a plasmodium, or “true slime mold” amoeba, is able to find near-optimal solutions to the Traveling Salesman Problem in linear time – meaning that adding more cities does not result in a huge increase in the amount of time our slimy friend takes to find an answer.
anna says:
Thank you for your post. I have read through some similar topics! However, your post gave me a very special impression, unlike other articles. I hope you continue to have valuable articles like these or more to share with everyone! crossword puzzles