6 ms·
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 t
by jadar 8y ago
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?
- hannasanarion 8y agoNope. The amoebae found solutions, but not optimal solutions.
- thaumasiotes 8y agoThe second one. You can also do approximations by letting a soap bubble film collapse.
- lainga 8y agoI 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 https://en.wikipedia.org/wiki/Spaghetti_sort
- JoshuaDavid 8y agowouldn't that be O(N^2) because it takes longer to sweep your hand over the spaghetti if there is more spaghetti?
- lainga 8y agoWell, 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.
- whatshisface 8y agoIf a Turing machine can have an infinite tape then a spaghetti pusher can have infinite palms.
- aasasd 8y agoRather idiosyncratically, this algorithm is prone to breaking the items being sorted.
- TheOtherHobbes 8y agoOften a problem for spaghetti code techniques.
- quickthrower2 8y agoAre we still talking pasta, or badly written OO code!
- sorokod 8y ago"arbitrary-precision real numbers"? You can tell apart two different pieces with |spaghetti1 - spaghetti2| < epsilon for arbitrary small epsilon?
- lainga 8y agoWe also assume access to arbitrarily long spaghetti and ignore concerns like relativistic effects or free breaking length.
- adrianN 8y agoThis 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.
- bno1 8y agoMaybe 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.
- ychen306 8y agoNo 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.
- resource0x 8y agoit 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.
- emtel 8y agoAbsolutely not. See my top level comment: https://news.ycombinator.com/item?id=18737321 https://news.ycombinator.com/item?id=18737321