Amoeba finds approximate solutions to NP-hard problem in linear time
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.