If you’ve ever had the chance to take an introductory class on CS, you might have come across the traveling salesman problem.
It’s a classic problem that deals with the complexity and challenges you’ll face as a computer programmer.
The problem goes like this: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?”
Stated another way, imagine you’re a salesman and you need to visit different cities to sell your product. You want to visit a set amount of cities (number of cities is denoted “N”), you only need to visit them once, you don’t care what order they’re in, and your only goal is to minimize the distance you need to travel.
While on the surface this seems like an easy problem that Google Maps can help you remedy, this is actually a very tough lesson in optimization (something we care a lot about in Blockchain). Optimization in this sense often means a solution that is cheaper, shorter, or faster. In Graph Theory, this is known as a Hamiltonian Path.
So, to demonstrate why this is hard, when you have N cities, you have N – 1 factorial possibilities. When N = 10 cities, that means there are over 180,000 combinations to try (9! / 2 = 181,440).
Suddenly, this isn’t a fun little puzzle and is actually a monster. We classify this type of problem as NP-Hard, meaning that even if you broke up the problem into smaller bits (as engineers like to do), the subproblems are still as complex as the original problem.
To save you the effort, there is no simple mathematical formula to find the most efficient route for our salesman in the TSP. Instead, you’ll have to calculate the length of each route and figure out which one is the shortest.
What’s worse is that for every city you add to N, the problem becomes exponentially harder. N = 4 means there’s only 3 different solutions to consider. But if N = 6, now there’s 360 to consider. And like we saw, once you start getting into the double digits for N, the possible routes become enormous.
As I said, the TSP is classified as NP-Hard, meaning the problem gets harder exponentially. We can also think of cryptocurrency mining as having this complexity scheme. The more hash power (N) that is added to the network, the more complex the problem becomes.
Because these kind of problems deal with cryptography, which deals with security and in our case the efficiency of the blockchain network, we’re obviously very concerned with solving these problems as quickly as possible.
So, let’s talk about an interesting development that was shared this week that dealt with this very proposition.
We learned that researchers from Keio University built a device for solving the TSP. What’s interesting about that is they didn’t just use an algorithmic solution; they used an amoeba.
That amoeba is the Physarum polycephalum slime mold.
Physarum polycephalum is a very simple organism that does two things: it moves away from light and it moves towards food (just like my reclusive brother). Evolution has made this amoeba abnormally efficient at both of these things.
That efficiency is exactly what they used to solve the TSP faster than traditional algorithms. They orchestrated their experiment in such as way that the amoeba would extend into channels and those channels represented cities. Extending into a channel representing a city affected the likelihood that a light will go off in channels representing the next cities on the route.
The “further” away that city was in the model, the more intense the light would be.
So, what does that mean?
Essentially, instead of having to calculate every individual path like traditional algorithms would do, the amoeba just passively reacts to the conditions it is presented with. It figures out the best possible path simply by enforcing the binary of food good, light bad.
The researchers arranged to put the organism on a plate with 64 channels corresponding to 8 cities (A-H) and their order in the final result. So if the best route is ABCDEFGH, that would correspond to A1, B2, C3, and so on. Since the channels offer food, the amoeba tries to spread out into all of them. A camera reads the results and arranges for light to shine on channels that represent long-distance paths.
The amoeba will retract from those channels. However, the volume of the creature remains constant, so retracting in one spot will cause other spots to extend just as extending in one area will cause other spots to shrink. It can’t, after all, create new mass. Because the creature also has a bit of randomness, it will sometimes overreach and not get stuck in a local maximum.
Remember when I said that when you add more cities to the TSP, it becomes exponentially harder?
That’s not the case with the Physarum polycephalum slime mold.
So, this amoeba can solve an NP-Hard problem faster than any computer algorithm.
Scientists conducted an experiment where an ancient fungus (slime mold) was incentivized to recreate the Tokyo subway system. Each subway stop (node) was marked with the slime molds favorite food (oat flakes).
After a short while, the slime mold grew to connect all the nodes/stops in a more efficient design than the centrally planned committee of engineers hired by the Japanese government.
From the Abstract:
Transport networks are ubiquitous in both social and biological systems. Robust network performance involves a complex trade-off involving cost, transport efficiency, and fault tolerance. Biological networks have been honed by many cycles of evolutionary selection pressure and are likely to yield reasonable solutions to such combinatorial optimization problems. Furthermore, they develop without centralized control and may represent a readily scalable solution for growing networks in general. We show that the slime mold Physarum polycephalum forms networks with comparable efficiency, fault tolerance, and cost to those of real-world infrastructure networks — in this case, the Tokyo rail system. The core mechanisms needed for adaptive network formation can be captured in a biologically inspired mathematical model that may be useful to guide network construction in other domains.
When you think of the costs and complexities involved in such an infrastructure project, it’s quite sobering to realize a slime mold can design a better network in a single day.
Unfortunately, the exact mechanism that the amoeba uses to determine the shortest route is still a mystery to the researchers. So, no, you won’t be able to mine Bitcoin with amoebas anytime soon.
But if they can figure out exactly how the amoeba works and translate that into code, we could see this trick used for solving all sorts of difficult computational problems.
In a way, it would do to computer security and cryptocurrency what graphene has done to material science.
One small amoeba could change the face computing forever, just like Satoshi.
Satoshi understood the power of the slime mold.
Bitcoin is a non-sovereign monetary good that pushes complexity and decision making to the edge just like fungi. Over time, this free market decentralization allows bitcoin to out-compete various legacy financial systems who have little skin in the game, suffer from the innovator’s dilemma, become more fragile over time, and often drown in bureaucracy (or worse).
Mycelium has no “central point of control.” Any individual part can be removed but the system as a whole survives.
Bitcoin functions the same way: as any one developer, node, miner, exchange, or user may be vulnerable yet not crucial for its survival. No one to jail, no one to shut down, no essential hardware to seize. Anytime one attacks bitcoin/mycelium but don’t successfully kill it, the system gets stronger.