Amoeba is the simplest creature that we go to school on one of the first lessons of biology. Hardly anyone considers the amoeba of highly intelligent individuals, because she doesn’t have a nervous system in the usual sense. However, a group of scientists from Tokyo’s Keio University have used this single-cell organism to solve mathematical problems. And to the surprise of the amoeba coped with it faster and more efficiently than a powerful computer.
The problem had to be solved, is called “the task of kommivojazhera”. It is this: imagine you’re a salesman, moving from town to town, selling their wares. You need to be as efficient as possible to earn as much money as possible, so you want to find the shortest path that will allow you to get to every city on the route. There is no mathematical formula to find the most efficient route. The only way to solve the problem is to calculate the length of each route and see which one is the shortest.
But that’s not all: the distance calculation becomes more difficult the more cities added to the route. For 4 cities, there’s only 3 routes. But for 6 of them already 360. This makes “traveling salesman problem” one of the problems that scientists call “NP-hard”. That is the problem, the complexity of which increases exponentially even for a small increase in performance. To the same type of tasks include, for example, mining cryptocurrency, so finding their solution is quite important today.
In their work, the Japanese scientists used the amoeba Physarum polycephalum, and more specifically — its slime, which it distributes as a “scout”. Being placed in a special chamber, which had a variety of channels. At the end of each of the channels, the researchers placed a bit of water. When the amoeba was getting water in one of the adjacent channels lights dimmed. The channel in this case were analogue the way from the task.
When the amoeba reaches the water, it affects the probability that the light will go off in channels, which are the next cities on the route. The farther away the city, the more his channel will be off the light. It may seem incredible, but the addition of new “cities” did not increase the time needed to spend on the solution and the path channels always remained the shortest. Unlike the computer, the amoeba did not need to calculate each distance to compute the optimum. Instead, it responds to the changing conditions and determines the best possible trajectory.
“The mechanism that affects the speed of decision-making amoeba and how it calculates the shortest path is still a mystery. Having established this, we can find the way of rapid solution of complex computational problems and even improve security.” says the study’s lead author Masashi Aono.