News for hackers. Stuff that matters.
Re:Electronic amoeba finds solution to traveling salesman pr... by dzaragozar on Sunday December 13, 2020 @05:42PM (#25411147)
Please fix the title, it is absolutely wrong. “Electronic amoeba” finds approximate solution to traveling salesman problem in linear time
Re:Electronic amoeba finds solution to traveling salesman pr... by jtsiskin on Tuesday December 15, 2020 @12:26AM (#25427319)
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.
Re:Electronic amoeba finds solution to traveling salesman pr... by polemic on Sunday December 13, 2020 @01:42PM (#25408921)
For clarity: an approximate solution
Re:Electronic amoeba finds solution to traveling salesman pr... by dnautics on Sunday December 13, 2020 @05:34PM (#25411093)
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)?
Re:Electronic amoeba finds solution to traveling salesman pr... by hpcjoe on Sunday December 13, 2020 @02:11PM (#25409171)
Analog computers for the win.
Re:Electronic amoeba finds solution to traveling salesman pr... by blamestross on Sunday December 13, 2020 @02:17PM (#25409231)
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.
Re:Electronic amoeba finds solution to traveling salesman pr... by karmakaze on Sunday December 13, 2020 @04:31PM (#25410489)
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.
Re:Electronic amoeba finds solution to traveling salesman pr... by blamestross on Sunday December 13, 2020 @05:13PM (#25410891)
> 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.

Re:Electronic amoeba finds solution to traveling salesman pr... by blamestross on Sunday December 13, 2020 @05:09PM (#25410859)
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...