Amoeba finds approximate solutions to NP-hard problem in linear time

m.phys.org

4 pointsdanielam1 comment

For anyone interested in looking at this story in depth, here are some of the times it or similar stories have been submitted to HN. Some of these submissions have comments and discussions, and those might be interesting to read too. Note that these are not all the same story, but they are all talking about "solving" things like TSP using slime-moulds or other organisms.

My take is this: No, they're not really doing anything interesting other than search, and no, they're not "solving" the TSP. Not least, given larger instances, they don't always find the minimum path, and they don't even find necessarily good paths. So while they do find a path, it really doesn't have any impact at all on the question of solving NP problems.

None.

If someone disagrees with that then I'd love to have a decent discussion.

https://news.ycombinator.com/item?id=18787254

https://news.ycombinator.com/item?id=18784956 (1 comment)

https://news.ycombinator.com/item?id=18775638

https://news.ycombinator.com/item?id=18774656

https://news.ycombinator.com/item?id=18771244

https://news.ycombinator.com/item?id=18765134

https://news.ycombinator.com/item?id=18750018

https://news.ycombinator.com/item?id=18746032

https://news.ycombinator.com/item?id=18745530

https://news.ycombinator.com/item?id=18735903 (76 comments)