An Amoeba-Based Computer Found Solutions to 8-City Traveling Salesman Problem
motherboard.vice.com
motherboard.vice.com
[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
[1] https://phys.org/news/2012-03-slime-mold-mimics-canadian-hig...
[2] https://phys.org/news/2012-10-slime-molds-spatial-memory.htm...
[3] https://royalsocietypublishing.org/doi/10.1098/rsos.180396
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.
Furthermore, both this and the main article are about finding suboptimal solutions, which is fun but not groundbreaking.
... the slime mold connected itself to scattered food sources in a design that was nearly identical to Tokyo's rail system.Generally speaking, "playing god" is talked about as messing with nature and the things around us to better suit our needs. Genetic engineering, climate engineering, etc. "God" refers to the natural order of things and trying to change it.
There are good heuristic, specially if the distances are not chosen at random but are the distance between points in the plane. So it's posible in some cases to find quite good solutions.
The problem is NP-complete only is you ask for the best solution.
(Form time to time there are articles that try to explain why analog computers are better than binary computers. Usually they assume infinite precision, that is impossible in a real system.)
The article claims that the time is linear, but it use quadratic space. So if you campare thy to simulate the algorithm with a big system in a sequential computer you will get probably cubic run time.
A better way to understand this is that the amoeba uses a good heuristic to solve the TSP in a small case. There are many heuristics out there, so it would be nice to implement this heuristic and compare with all the other one is some kind of standardized example set. It's more easy to find a good solution in a small system.
(Under the hood, the amoeba is a quantum system. But if you consider this a quantum computer then your phone is also a quantum computer.)
The internal communication inside the cell is classical, not quantic (classic, like your phone). I guess it use some kind of internal hormone, but it may be some signal that propagates in the cell membrane. IANAB.
You can't have a good quantum correlation in something that is as big as a cell (unless you freeze it at ridiculous low temperature that are not posible for now and would kill the cell anyway, or you have a more ordered system like a extremely pure crystal, or you only want some correlation for ridiculous small amount of time).
You can have big entangled systems, but they look more like pair of very clear optic fiber, not like a cell with a lot of water and crap moving randomly inside.
There are also some interesting "big" quantum effects in molecules like chlorophyll. (I'm not sure if they are 100% confirmad yet.) But a molecule of chlorophyll is much much much smaller than the cell and the effect is very short lived.
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.
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 :)
This is wrong.
"the decision version of the TSP (where, given a length L, the task is to decide whether the graph has any tour shorter than L) belongs to the class of NP-complete problems." (https://en.wikipedia.org/wiki/Travelling_salesman_problem)
If amoeba gives me a proposed solution to the TSP, I can easily check if said amoeba is right or wrong. You are right that I don't know how close it is but I know if it's right or wrong. And this should be enough because we already have close-enough approximations of the TSP.
Also your definition of NP-hard is wrong: you're right that it is "at least as hard as any NP problem" but the conjunction of this with "its solutions can't be verified in polynomial time" is false, because the definition of a NP problem is that its solutions can be verified in polynomial time.
Also, this is not interesting because problem instance is small is not always a good argument. An implementation of a quantum algorithm factoring 15 into 5 and 3 is interesting, even though it is trivial.
Also, you're wrong about being able to verify a solution easily. The decision version of the TSP is NP-complete, which means you can't solve it efficiently unless you can solve NP complete problems. You're confusing _solving_ the decision problem with _verifying a solution_ to the decision problem.
- 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.
https://news.ycombinator.com/item?id=18726441
You can also do approximations by letting a soap bubble film collapse.
> 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.
https://link.springer.com/referencework/10.1007%2F978-1-4939...
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.
What's next? Amoeba-resistant encryption algorithms?