Electronic amoeba finds solution to traveling salesman problem in linear time

global.hokudai.ac.jp

27 points·wjSgoWPm5bWAhXB··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.

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...

> 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.

Reply on news.ycombinator.com