Nice 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.]
One 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...
>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.
So 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.
ive 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.
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.
"Playing God" is often used for activities where we're able to cause some change, have a hard time undoing our actions, and are unable see all possible consequences.
I 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.
No, if I understood right, this thing is a quantum computer solving NP-complete problems in linear time. And the article claims to have a simulation doing the same, but they are not sure whether this is actually only a special case scenario.
It's not a "quantum computer". It's an analog computer instead of a binary computer. It can be simulated with a normal (binary) computer using floating point numbers (remember that the amoeba has a finite precision).
(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.)
Yeah I guess in order to make this into a simulation, one would effectively add all the exponential time back, since it requires all that to "run" an amoeba on a classical computer. In that article they mention the organism communicating across its body, i.e. reacting to stimuli in all parts in a correlated fashion, that is the bit referring to a quantum system. Of course all physical systems are quantum systems (if I actually had a phone that one too yes, although the operating system does not make use of its nature). So there is no question whether we can simulate that algorithm, it cannot be possible without calculating all the parts, and that is no longer linear time.
> In that article they mention the organism communicating across its body, i.e. reacting to stimuli in all parts in a correlated fashion, that is the bit referring to a quantum system.
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.
Right, it is not guaranteed to find _the_ best solution possible, but at least it does find _some_ solution to NP-complete problems in linear time, which no classical algorithm is expected to be able to do. Now they claim in that article to have made a simulation of this running on a classical computer exhibiting the same characteristics, which frankly should not be possible. so where is the catch?
You can always find a solution to the TSP. All cities are connected with all cities, so you can travel the cities in the alphabetical order (or the order in list). It's (usually) a very bad solution that is much longer than the best solution.
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.
You can't say anything about the runtime of amoeba because they only solve a finite number of instances and you have no accurate model that would allow you to say something about the asymptotic behavior.
This 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.
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 :)
> You can't solve the problem instance yourself, so you don't know how close it is to the optimum.
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.
My definition isn't wrong - NP-hard is a superset of NP. There are problems in NP hard whose solutions can't be verified in polynomial time.
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.
A 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.
The 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.
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?
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.
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.
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.
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.
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.
Good 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
...
If this interests you, Springer just published an encyclopaedia on ‘Unconventional Computing’, which includes a chapter from Hal Abelson and Gerry Sussman
Interesting, 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.
Not 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.
[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
[4] https://en.wikipedia.org/wiki/Slime_mold