paulandscruffy.wordpress.org

One of the most challenging problems in theoretical computer science has been solved. Kind of. It was solved, moreover, not by researchers at MIT, Cal Tech, or Carnegie Mellon, but by bumblebees. Scientists researching the critters at Queen Mary and Royal Holloway  of the University of London noticed that the bees were able to quickly and accurately identify the shortest possible distance they needed to travel in a day of pollen gathering. How the bees are able to do this is still unclear.

The corresponding human challenge is quite simple: given a set of cities, and an associated cost of travel between each city, what’s the cheapest way to visit all of them and return home at the end of the day? Despite its innocent sounding structure, the problem belongs to a family collectively known as NP-hard. This means that algorithms which solve the problem are all exponential in running time, so subtle increases in the data set lead to immensely slower problem solving times. While a polynomial-time algorithm might take several days to solve, a very large problem such as an exponential-time algorithm could take many times the age of the universe to solve. The difference only grows with the input size.

Bees model this problem by gathering nectar from flowers. The bees in the experiment were monitored as they learned the location of a number of flowers. Later, it was observed that the bees were taking the shortest possible route to visit all of the flowers and return home. For the set of flowers the bees discovered, they had managed to find an optimal solution to the travelling salesman problem and implement it, despite having a brain thousands of times smaller than the humans they tend to terrorize.

But some national media sources may have overestimated the bees’ capabilities. The original problem is slightly more complicated than what the bees managed to solve. The primary difference is that the number of flowers the bees solved the problem for is limited, while the travelling salesman is interested in visiting any possible number of cities with any possible set of connections and costs. Additionally, the travelling salesman may not be able to move between some cities, as there is no connection, whereas the bees could move freely from any flower to any other flower. Consider a bee confronted with one trillion flowers, some of which cannot be flown between. The bee would likely be unable to solve the travelling salesmen problem for this set of flowers, which more accurately represents the true problem.

While the bees have not, in fact, solved the set of NP-hard problems, they have nonetheless demonstrated a remarkable capability of nature. For an insect with such a small brain to be able to solve a problem which could keep your laptop busy for days is quite impressive. While the methods the bee uses to remember and traverse the flowers are unknown, one thing is sure: bees will do anything for some nectar.