9 ms·
An Amoeba-Based Computer Found Solutions to 8-City Traveling Salesman Problem
- justicezyx 8y agoGood analogy for human to be computing organisms developed unnoticer self awareness to a higher level beings. Maybe they are now debating if the things they created really are self-conscious ...
- dleslie 8y agoWe are computing the answer to the ultimate question.
- deleted 8y ago[deleted]
- module0000 8y agoI thought we were computing the question, since the answer is known to be 42.
- jadar 8y agoThe real question is can the question be solved, or is it undecidable? If undecidable, how to reduce the Halting Problem to it? ;)
- justicezyx 8y agoNow I know why human have a thing called emotions, that must be the randomness injected by the system!
- izzydata 8y agoPay no mind to the really low budget visuals. This video is quite the mental roller-coaster and related to this topic. https://www.youtube.com/watch?v=CN_eL5ukCbw https://www.youtube.com/watch?v=CN_eL5ukCbw
- brg1007 8y agoSo if I understood well the concept, this type of amoeba is like an ASIC for traveling salesman problem. Interesting concept, to find bio-organisms that can be used very efficentlly to "solve" a certain type of problem.
- sano1 8y agoHopefully our spiritual and intellectual betters will start to leverage humans this way. The future is bright.
- oilfun 8y agoor just let people be themselves and stop trying to play god
- ozzmotik 8y agoive never heard a convincing argument for why it's necessarily a bad thing to "play god". it just seems like an oft repeated phrase that makes no sense to me and only survived because of some idea that we have no right to try and discern the true nature of the universe and then to control it in the pursuit of betterment of our capacities as a species.
- vxxzy 8y agoI wouldn't necessarily say "playing god", but we do vaccinate ourselves right? I mean I think the real issue is inflicting a change to a being that will become "Sentient" or "Conscious". When we genetically alter that which has potential for "life", do we know, beyond a doubt, that the change we inflict will be positive for the individual AND positive our species as a whole? If we cannot say for certain, then genetically altering sentient life (who have no choice), is not a good idea.
- NotAnEconomist 8y agoBecause a lot of "playing god" is thinly veiled authoritarianism -- the desire to control our fellows, out of our own egotism?
- KineticLensman 8y agoNice for the amoeba, but slime molds have first mover advantage. They solved the travelling salesman problem in 2013, and they managed 20 cities [0]. [edit: my bad: the two reports referred to amoeba and slime molds but are actually discussing the same species (Physarum polycephalum)] [edit 2: it's been pointed out that the 2013 creature I referenced wasn't even real, just a sim. However, real slime molds can model Canadian transport networks [1] and can use slime trails to navigate around obstacles [2]] [Edit 3. The Vice article says 'Amoeba' but references a Royal Society [3] story that says 'slime mold'. Wikipedia [4] says that slime molds comprise the mycetozoan group of the amoebozoa. So slime molds are in fact amoeba, but not all amoeba are slime molds.] [0] https://phys.org/news/2013-03-blob-salesman.html https://phys.org/news/2013-03-blob-salesman.html [1] https://phys.org/news/2012-03-slime-mold-mimics-canadian-highway.html#nRlv https://phys.org/news/2012-03-slime-mold-mimics-canadian-hig... [2] https://phys.org/news/2012-10-slime-molds-spatial-memory.html#nRlv https://phys.org/news/2012-10-slime-molds-spatial-memory.htm... [3] https://royalsocietypublishing.org/doi/10.1098/rsos.180396 https://royalsocietypublishing.org/doi/10.1098/rsos.180396 [4] https://en.wikipedia.org/wiki/Slime_mold https://en.wikipedia.org/wiki/Slime_mold
- yorwba 8y agoThe work in 2013 appears to have been a simulation of slime mold/amoeba behavior, not an actual living organism.
- jacquesm 8y agoOne slime mold to another: It just might be that these artifacts of quantization we see are proof we are living in a simulation. In fact, there is this argument to be made that the chances that we live in a simulation are bigger than that we do not. Here, let me show you...
- deleted 8y ago[deleted]
- whatshisface 8y ago>It just might be that these artifacts of quantization we see The artifacts of quantization that we see are of the kind that come from continuous differential equations, not the kind that come from a lattice. Even the qbits in a quantum computer are found on a continuous Bloch sphere, instead of a discrete zero or one state space.
- DmitryOlshansky 8y agoWhen it comes to biocomputing nothing beats humans challenged with “impossible” problems and decent amount of time.
- angel_j 8y agoIndeed, I bet 4chan could solve this faster than amoeba.
- vbezhenar 8y agoThat would make a fun experiment.
- i_am_nomad 8y agoLower collective IQ though.
- Izkata 8y agoReally doesn't seem like it when stuff like The Haruhi Problem pops up: https://mobile.twitter.com/robinhouston/status/1054637891085918209?s=21 https://mobile.twitter.com/robinhouston/status/1054637891085...
- whatshisface 8y agoThat can also be read as an indictment of our ability to give time estimates. ;)
- jadar 8y agoSo 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.
- jarmitage 8y agoIf this interests you, Springer just published an encyclopaedia on ‘Unconventional Computing’, which includes a chapter from Hal Abelson and Gerry Sussman https://link.springer.com/referencework/10.1007%2F978-1-4939-6883-1 https://link.springer.com/referencework/10.1007%2F978-1-4939...
- mindcrime 8y agoInteresting, I never knew there was a conference series on "Unconventional Computing"[1] until just now. Sadly they publish their proceedings through Springer, instead of PMLR. That said, at least some of the older proceedings can be found using the usual pirate sites if one is so inclined. [1]: https://ucnc2018.lacl.fr https://ucnc2018.lacl.fr [2]: http://proceedings.mlr.press/index.html http://proceedings.mlr.press/index.html
- deleted 8y ago[deleted]
- devy 8y agoMultiple reposts from the last 2 days: https://news.ycombinator.com/item?id=18726441 https://news.ycombinator.com/item?id=18726441 https://news.ycombinator.com/item?id=18729284 https://news.ycombinator.com/item?id=18729284 https://news.ycombinator.com/item?id=18725828 https://news.ycombinator.com/item?id=18725828
- hpcjoe 8y agoSo ... this is a Turing complete bio-organism? I wonder if we can get them to solve the towers of Hanoi problem ...
- exabrial 8y agoSpoiler, this is not https://en.wikipedia.org/wiki/Amoeba_(operating_system) https://en.wikipedia.org/wiki/Amoeba_(operating_system)
- nikofeyn 8y agowhy would it be?
- zachguo 8y agoSearch "evolutionary dynamics" and "complex adaptive system".
- emtel 8y agoThis is a non story, at least insofar as it concerns complexity. The result would be no more or less interesting if the amoebas sorted an array or did some other polynomial time task. Here's why: 1. Finding approximate or near-optimal solutions for hard optimization problems is almost always easy. So in this case, an amoeba did something that is also easy to do with a classical computer. 2. 8 is a small number. There are 8! possible paths, which is about 40,000, which means you could find the optimal solution to this problem in a millisecond or two with a classical computer. To be remotely interesting, you'd need to solve a TSP for a number like, say, 50 or 100. 3. Even if you had an amoeba that somehow could find solutions for large numbers of cities, how would you know? You can't solve the problem instance yourself, so you don't know how close it is to the optimum. This is because TSP is not in NP, which are the set of problems whose solutions can be verified in polynomial time. Rather, its NP-hard, meaning its at least as hard as any NP problem, but its solutions can't be verified in polynomial time. So if amoebas had some magic TSP solving algorithm, we probably wouldn't be able to tell that they did unless we had our own magic algorithm to test it against. 4. Also, even if the amoeba could solve this optimally for large instances, _most_ instances of hard problems are actually easy. Therefore, simply showing that the amoebas can do this for some finite number of instances is not sufficient. An efficient algorithm for TSP or some other hard problem has to be able to solve _any possible instance_ efficiently, in order for this to have any implications for questions like P=NP. So if you wanted to show that amoebas had a magic TSP algorithm, you'd have to formally prove that their algorithm works on all instances. Since amoebas themselves are not easily formalizable, I don't see how you'd do this.
- algorias 8y ago>> This is because TSP is not in NP Um, the decision version of TSP (does there exist a Hamilton path of length at most x?) is definitely in NP. It is also NP-hard (your definition of NP-hardness is wrong). I guess what you're trying to say is that the optimization version of TSP (find the shortest Hamilton path) cannot be verified in polynomial time, as this would require answering the decision version of TSP in the negative for some length x, and this is hard to verify since TSP is not in co-NP. In spirit, your comment is absolutely spot on. But as we all know, technically correct is the best kind of correct :)
- the_other_guy 8y agoLeonard Adleman did lots of research about that 25 years ago. It's now known as "DNA Computing"
- keefhowie 8y agoWhat am I missing here? The amoeba reacted predictably to lights turning on and off. In what way does that constitute problem solving?
- xyproto 8y agoIsn't this what quantum computing wanted to achieve? What's next? Amoeba-resistant encryption algorithms?
- QML 8y agoNot really: NP-hard problems are a set of a decision problems "does a route shorter than x exist?" while in quantum computing, we know an answer exists but the question is obtaining it. E.g. the factors of a number always exist.
- thekhatribharat 8y agoA couple of questions (some of them might be stupid :)) - It says they used a neural network to control illumination in different channels, so the total time complexity should consider neural network + amoeba system for calculations. - When you put the amoeba in a environment with a vastly large number of channels, does it still behave the same? I mean, does it scale? Maybe amoeba becomes less averse to illumination with increase in number of channels and you get progressively worse solutions to TSP.
- salamanderman 8y agoThe neural network is like the plate itself, fixed at least for any configuration of N cities. Interpret that as you will. The plate itself has N^2 channels.
- black_13 8y agoThe amoeba will be given H1b status.