back
9 comments
Please fix the title, it is absolutely wrong. “Electronic amoeba” finds approximate solution to traveling salesman problem in linear time
Yeah, I was pretty shocked to see that some amoeba just solved P=NP, and that it wasn’t even on the front page of HN.
For clarity: an approximate solution
assuming the slime mould has standard unconstrained biological reproduction properties (over the time of the experiment) isn't the space/resource complexity here O(2^t)?
Analog computers for the win.
Give me O(N) processors to solve an O(N^2) problem and I could do it in O(N) time too. The whole trope "slime mold solves TSP" is overblown.
TSP is NP-hard, like 2^N. The trick is that it's approximate not exact. This could be of interest compared to known heuristic algorithms.
> This could be of interest compared to known heuristic algorithms.

The problem is that it isn't. Yes, a big enough cellular automaton can be used to solve problems, but the ratio of "processors" to "problem" isn't practical and we are not learning anything to improve heuristics because the "solution" here is only practical on a 2d surface.

It is on a planar surface, with a low amount of points. Approximating it to arbitrary precision with 1 processor is polynomial. https://en.wikipedia.org/wiki/Travelling_salesman_problem#Eu...