You might not think that a one-cell life form can easily solve a data problem that has vexed programmers for decades. To reach bread crumbs. But several studies over recent years show precisely that.
The Traveling Salesman Problem (TSP) is “one of the most intensely studied problems in computational mathematics.” (University of Waterloo Mathematics) Also one of the oldest. Picture a traveling salesman who wants to minimize time and expenses while reaching potential customers. “Given a set of cities and distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point.” (Geeks for Geeks)
How hard is the problem?
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 complexity is due to the large number of possible solutions. For example, for four cities, there are only three possible routes. But for eight cities, the number of possible routes increases to 2520. Lisa Zyga, “Amoeba finds approximate solutions to NP-hard problem in linear timearticle title” at Phys.org
For six cities, there are 360 routes. For ten cities, there are millions of routes.
The rapidly mounting math is not merely a theoretical headache. It hinders the development of defenses against hacking encrypted systems. Admittedly, Keio University’s approach, putting a slime mold of amoebas (Physarum polycephalum) to work, is unusual but it makes some sense.
The amoeba* moves by extending temporary projections from its loosely organized single-cell body to lever itself along. These short-lived pseudopodia (“false feet”) can also take in food, typically a variety of bacteria, algae, and plant-based materials encountered along the way. When amoebas encounter a food shortage, they can also form slime mold, a “great swarm” acting efficiently as one organism, with one goal in mind: avoid imminent death by starvation.
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.
Each channel represents a city on the “salesman’s route” with lights going off that signal how far each next “city” is.
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. Avery Thompson, “A Single Cell Hints at a Solution to the Biggest Problem in Computer Science” at Popular Mechanics
The thinking if, if we could figure out just how the brainless amoebas do these calculations, we might be able to use that information to speed up problems that are difficult because they use up a lot of computational power, including cybersecurity problems, which the amoebas do not seem to require.
Apart from solving computer science problems, the amoebas’ skills raise some interesting questions. Though we don’t know how, we know that some type of intelligence can exist without a brain, as the slime mold has demonstrated in other experiments, reminiscent of the Travelling Salesman problem, as well:
Consider Dictyostelium discoides, one of the 900 species known as slime mold. Don’t let the disgusting name deter you; the example is informative. Faced with a food shortage, thousands of brainless, one-celled amoebas living underground hurry to form a single blob. The blob lengthens to about 1/25 of an inch (or one millimeter) and resembles a tiny slug. Then the “slug” crawls toward light, like a worm, and thus arrives at the soil surface.
Different amoebas play different roles inside the blob/slug. Some enable it to move. One percent behave like police: they crawl around looking for infectious bacteria. If they find one, they ingest it and leave the blob. They die, but the slug survives.
Once above ground, the slug reorganizes itself into something more like a fungus. Some of the amoebas form a stiff stalk, while others make their way to the top and become a sticky ball. They then attach the whole slime mold to an animal’s foot. Having secured a means of transportation, they drop off where a food source is found. Then they all disperse as one-celled creatures again. Denyse O’Leary, “Sublime Mold” at Salvo 24, Spring 2013
A few years ago, a researcher, using a map of Canada and some cereal, demonstrated in a novel way that slime mold is
fantastically efficient at finding the quickest route to food. When he placed rolled oats over the country’s population centers and a slime mold culture over Toronto, the organism grew its way across the Canadian map, sprouting tentacles that mimicked the Canadian highway system. It’s an experiment that’s been replicated globally several times now—in Japan, the UK, and the United States—all with a similar outcome. Rebecca Jacobson, “Slime Molds: No Brains, No Feet, No Problem,” at PBS Newshour (Apr. 5, 2012)
When we hear hype about machines that will soon out-think people, we might put it in perspective by recalling that we still struggle to build a machine that can out-think amoebas looking for crumbs.
*Note: What type of life form is an amoeba? LiveScience explains that “The term “amoeba” refers to simple eukaryotic organisms that move in a characteristic crawling fashion.” They are similar in their appearance and lifestyle, not necessarily in origin. Their cells, unlike those of bacteria, have a nucleus.
See also: Can plants be as smart as animals?