Dwood15 sent me the following quote from the comments of a similar article on Gizmodo. It makes some excellent points and further demonstrates the failing of the media's 'explanation' of this interesting discovery:
Time for the usual corrections to a wildly misleading story (not really Giz's fault, but PopSci- you're earning that "Pop").
There is absolutely nothing in the university press release (the paper isn't out yet) that says that the bees solved this problem in any way faster or more efficiently than a computer. All they really said is that bees solved a small example of the Travelling Salesman problem. Period.
They say that bees solved the Traveling Salesman problem, which "can" keep a supercomputer busy for days. That is one of the most misleading statements I've read for a while. The traveling salesman problem is a general class of problems. There are an infinite number of examples of that problem. The version that the bees solved is not one that would take a supercomputer days; a computer could solve it in a tiny fraction of the time the bees could.
The reason this problem is important is that NP-hard problems *scale* at a worse-than-polynomial slowdown according to any known algorithm. A version of the problem with just a few cities, like the bees dealt with, can be solved very quickly by a computer, but as the number of cities and routes grows, the problem rapidly becomes infeasible to solve- it doesn't take that many cities before no known computer could solve it in the lifetime of the universe.
The versions of the problem that take a supercomputer days to solve, are much bigger examples that the bees would never solve.
Now, if they had shown by plotting the slowdown in the bee's algorithm, which is unknown, that the algorithm scales at a polynomial rate, then they would deserve a Nobel Prize, Field Medal, and Turing Award all at the same time, because knowing whether a polynomial-time solution can even exist to an NP-hard problem is one of the very most important open questions in science. But they didn't.