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

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

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.

1 Comment

  1. 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.

    Reply

Leave a Comment

Your email address will not be published. Required fields are marked *

*

*