Problem in Computer Science

A Single Cell Hints at a Solution to the Biggest Problem in Computer Science

One small amoeba found a solution to the traveling salesman problem faster than our best algorithms. What does it know that we don't?

By Avery Thompson


One of the oldest problems in computer science was just solved by a single cell.


A group of researchers from Tokyo’s Keio University set out to use an amoeba to solve the Traveling Salesman Problem, a famous problem in computer science. The problem works like this: imagine you’re a traveling salesman flying from city to city selling your wares. You’re concerned about maximizing your efficiency to make as much money as possible, so you want to find the shortest path that will let you hit every city on your route.

There’s no simple mathematical formula to find the most efficient route for our salesman. Instead, the only way to solve the problem is to calculate the length of each route and see which one is the shortest.

PHYSARUM POLYCEPHALUM IS A VERY SIMPLE ORGANISM THAT DOES TWO THINGS: IT MOVES TOWARD FOOD AND IT MOVES AWAY FROM LIGHT.

What’s worse, performing this calculation gets exponentially harder the more cities are added to the route. With four cities, there are only three different routes to consider. But with six cities, there are 360 different routes that need to be calculated. If you’ve got a route with ten or more cities the number of possible routes is in the millions.

This makes the traveling salesman problem one of a broad class of problems computer scientists call ‘NP hard.’ These are problems that get exponentially difficult very quickly, which also includes problems related to hacking encrypted systems and cryptocurrency mining. For pretty obvious reasons, a lot of people are interested in finding ways to solve these problems as quickly as possible.

Keio University's solution is different from the typical algorithmic solutions produced by other researchers, because the scientists used an amoeba. Specifically, the Physarum polycephalum slime mold. Physarum polycephalum is a very simple organism that does two things: it moves toward food and it moves away from light. Millions of years of evolution has made Physarum abnormally efficient at both of these things.

The Keio University researchers used this efficiency to build a device to solve the traveling salesman problem. They set the amoeba in a special chamber filled with channels, and at the end of each channel the researchers placed some food. Instinctively, the amoeba would extend tendrils into the channels to try and get the food. When it does that, however, it triggers lights to go off in other channels.

In this particular case, each channel represents a city on our hypothetical salesman’s route, along with the order that city should be visited. When the amoeba extends into a channel representing a city, it affects the likelihood that a light will go off in channels representing the next cities on the route. The farther away that city is, the more frequently the light will go off in that channel.

This might seem like a roundabout way of calculating the solution to the traveling salesman problem, but the advantage is that the amoeba doesn’t have to calculate every individual path like most computer algorithms do. Instead, the amoeba just reacts passively to the conditions and figures out the best possible arrangement by itself. What this means is that for the amoeba, adding more cities doesn’t increase the amount of time it takes to solve the problem.

So the amoeba can solve an NP-hard problem faster than any of our computer algorithms. How does this happen? The Keio scientists aren’t sure, exactly.

“The mechanism by which the amoeba maintains the quality of the approximate solution, that is, the short route length, remains a mystery,” says lead study author Masashi Aono in a press release.

But if the researchers can figure out just how the amoeba works, they can use this trick for more than just helping out traveling salesmen. It could speed up our ability to solve all kinds of difficult computational problems and change the way we approach security.

This one small amoeba—and the way it solves difficult problems—might just change the face of computing forever.