While most of us struggle to make a normal computer work, a group of scientists from Keio University in Tokyo, Japan decided to test if they can build computers using single-cell organisms known as the amoeba.

Remarkably, this is not a new concept, with several researchers in past have used different organisms including amoeba to calculate the shortest path between two points. However, the Japanese team of scientists went a step forward and instead of just calculating the shortest path, they set about computing a solution for a remarkably hard problem, known as “Travelling Salesman Problem“.

## So what is the Travelling Salesman Problem?

The Travelling Salesman Problem (TSP) asks a very simple

In computational terms, the TSP is classified as an NP-Hard problem, which in simple terms means, solving the problem becomes exponentially difficult if you add even one city.

### Why is TSP difficult to solve?

Travelling Salesman Problem is not difficult to solve, there are several algorithms that can be used to solve it. The issue is time that is required to implement these algorithms.

E.g. if you had 3 cities, you can even guess what would be the shortest route, for 4 you can still calculate using trial and error, for larger number of cities (known as nodes) you can still apply some heuristic algorithms that can generate an optimal solution (within 2-3% of the best possible solution). However, for 3 cities you might only need 2 minutes to come up with the answer, but for 300 cities, you will need 2^300 times more time. Such problems whose complexity increases exponentially with each additional node are classed under the NP-Hard problem explained earlier.

Formulating a solution for NP-Hard problems that can give results in “linear time” is the holy grail of computational science (and carries a $1 million reward from Clay Institure of Mathematics).

## Ok, how did the Amoeba’s manage it?

Biological computing devices in past have shown the ability to not just complement conventional computing systems but also surpass them especially in problems that require a lot of computations or calculations to solve.

The Amoeba, Physarum polycephalum which looks like a slime mould has been actively investigated to aid in such computational problems due to their ability to make correct decisions in uncertain environments.

### Harnessing the shape changing dynamics of plasmodium

The Plasmodium amoebas love food and hate lights and if you put a bunch of them somewhere they will move towards food and away from light, the Japanese scientists used this ability to create a computer by placing 64 small channels (or tubes) for the amoeba to go into. The amoeba naturally tried to cover as much surface as possible to extract nutrients however retreats from a channel when the channel is illuminated by light.

Each of the 64 channels, as you can see in the video is assigned a code (city name) to simulate the TSP. Additionally, each of these cities is also assigned a code 1-8 which denotes the order the city should be visited. E.g. if the slime extended to A2, C1, B3, C should be visited first, followed by A (2nd) and then B (3rd).

To simulate the distances between cities, the researchers created a neural network that would illuminate channels so that cities with greater distance are illuminated.

### Solving the NP-Hard problem

While the scientists simulated 8 cities, adding additional cities does not change the time required by the slime exponentially, but rather linearly.

**Source**: Royal Society Publishing**Via**: Vice

**The Authors of the ****original**** article**: Liping Zhu, Song-Ju Kim, Masahiko Hara, Masashi Aono