4 ms·
Electronic amoeba finds solution to traveling salesman problem in linear time
- polemic 6y agoFor clarity: an approximate solution
- hpcjoe 6y agoAnalog computers for the win.
- blamestross 6y agoGive 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.
- karmakaze 6y agoTSP 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.
- blamestross 6y agoIt 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#Euclidean https://en.wikipedia.org/wiki/Travelling_salesman_problem#Eu...
- blamestross 6y ago> 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.
- dnautics 6y agoassuming 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)?
- dzaragozar 6y agoPlease fix the title, it is absolutely wrong. “Electronic amoeba” finds approximate solution to traveling salesman problem in linear time
- jtsiskin 6y agoYeah, 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.