Hacker News Reader

Comment by jadar | Hacker News Reader

So does this mean that there is a polynomial solution to the Traveling Salesman problem (and by extension, every other NP-complete problem)? Or does this mean that the amoeba is just really good at approximating a solution to it, so it's either not a complete solution, or just solves the exponential problem really quickly?

View on HN

I would caution against equating the computational capacity of a physical entity like this with what a single Turing machine or equivalent can do. The classic example is that I can sort a bunch of arbitrary-precision real numbers in O(n) time using spaghetti: cut a piece to length for each number, then push the ends flat against a table and sweep your hand down along them while you repeatedly remove the first piece to touch your hand [0]. The pieces of spaghetti are able to do this because they're acting like a parallel computer; the thousands or millions of chemical reactions taking place inside the amoeba are probably doing the same thing.

[0] https://en.wikipedia.org/wiki/Spaghetti_sort

wouldn't that be O(N^2) because it takes longer to sweep your hand over the spaghetti if there is more spaghetti?

Well, really, it's more like O(n) cutting, O(m) sweeping (rather than O(1)) in the largest value m we are trying to sort, and thus the time it takes for your hand to go from the highest spaghetti to the table, and O(n) picking spaghetti out. In that sense it's like radix sort, but you could make a similar point for comparison-based sorts as well, e.g. sorting 1024-bit numbers on a certain-width architecture will take longer, because you need more operations per comparison. I think the point of the example is that lining the pieces up so that they can be picked out is constant-time, because they are physical objects and all either being pushed or falling under their own gravity. That's a good point, though, it assumes arbitrarily large (Andre the Giant?) hands.

If a Turing machine can have an infinite tape then a spaghetti pusher can have infinite palms.

Rather idiosyncratically, this algorithm is prone to breaking the items being sorted.

Often a problem for spaghetti code techniques.

Are we still talking pasta, or badly written OO code!

"arbitrary-precision real numbers"? You can tell apart two different pieces with |spaghetti1 - spaghetti2| < epsilon for arbitrary small epsilon?

We also assume access to arbitrarily long spaghetti and ignore concerns like relativistic effects or free breaking length.

This won't work in linear time, since you need time proportional to the square root of the number of spaghetti to move your picker from the position of the longest spaghetti to your output list.

The second one.

You can also do approximations by letting a soap bubble film collapse.

No to both. Note that these two problems are related because TSP is NP-hard to approximate.

> In this study, we show that the time taken by plasmodium to find a reasonably high-quality TSP solution grows linearly as the problem size increases from four to eight.

There is hardly any theoretical evidence to suggest a polynomial solution from this experiment.

Maybe it is able to solve the problem much faster than it looks but still with exponential complexity and yet its body takes a while to react in order for us to read the solution. Like being I/O bound.

Absolutely not. See my top level comment: https://news.ycombinator.com/item?id=18737321

it would be interesting to conduct the same experiment for N=9 and then N=10 and find out how it scales. Single case contains no information about the function in question.

Nope. The amoebae found solutions, but not optimal solutions.

Reply on news.ycombinator.com