An Amoeba Managed to Solve a Complex Mathematical Problem...Without a Brain

Thursday, 27 December 2018 - 1:02PM
Weird Science
Thursday, 27 December 2018 - 1:02PM
An Amoeba Managed to Solve a Complex Mathematical Problem...Without a Brain
< >
Pixabay composite
Math nerds will be familiar with the infamous "Travelling Salesman Problem" (TSP), but for those of you who don't obsess over computer algorithms or city planning, let's just say it's one of the most enduring mathematical problems ever devised, as well as a major benchmark used to test how quickly and how well a computer can solve a problem. Now a single-celled slime mold has demonstrated that it can find near-optimal solutions to it, and do so in impressive time.

The Travelling Salesman Problem usually goes like this: a travelling salesman wants to plan a trip to, say, 15 cities across the United States, but he doesn't want to travel extra miles if he doesn't need to. He also doesn't want to visit the same city twice, and wants to end the trip back where he started. Because these cities are scattered across the US, planning the shortest route that visits all of them exactly once turns into a difficult problem—even more so because you'd need to explore all the route options to ensure that there isn't a better route that you missed previously. If you add more cities to the problem, the time it takes a computer to "solve" the problem increases exponentially due to the proliferation of routes.

In the lingo of computer science, the TSP is an "NP-hard" problem, and a major challenge for optimization.

But according to a new study published in the journal Royal Society Open Science, a plasmodium, also known as a "true slime mold" amoeba, was able to solve a TSP problem involving four "cities," then eight. The experiment involved placing agar—a jelly-like food substance—in various locations in a petri dish and then setting the amoeba at the center of it all. From there, it was up to amoeba to find the optimal way to reach all the pieces of agar. What was interesting was that the time it took the amoeba to solve the eight-"city" problem wasn't an exponential increase from the previous four-city problem, implying that it had found a new way to "solve" the TSP that was more efficient.

According to Masashi Aono, the lead researcher on the study: "How the amoeba maintains the quality of the approximate solution, that is, the short route length, remains a mystery."
Science
Science News
Weird Science