Using A Slime-Mold To Calculate Minimum Spanning Trees | Hacker News Reader

Using A Slime-Mold To Calculate Minimum Spanning Trees

nytimes.com

68 pointsrfreytag20 comments

Open articleView on HN

http://news.ycombinator.com/item?id=1071093

http://news.ycombinator.com/item?id=1071533

http://news.ycombinator.com/item?id=1071568

http://news.ycombinator.com/item?id=1072876

http://news.ycombinator.com/item?id=3406446

http://news.ycombinator.com/item?id=3477746

http://news.ycombinator.com/item?id=3728933

http://news.ycombinator.com/item?id=3757527

http://news.ycombinator.com/item?id=3853748

Very few have comments, but the stories are varied.

I'm calling out this one because it has video, which I think people who read the NY Times article would like to see: http://phys.org/news/2012-03-slime-mold-mimics-canadian-high...

Soap films approximate minimum spanning trees. See: http://csunplugged.org/sites/default/files/activity_pdfs_ful... (see page 7 [aka, page 157]).

Actually, these films approximate Steiner Trees; which is harder (NP-complete): https://en.wikipedia.org/wiki/Steiner_tree_problem

EDIT: replaced 'find' and 'solve' with 'approximate.' EDIT: added '(NP-complete)'.

Also featured in this video: http://www.youtube.com/watch?v=dAyDi1aa40E

Only for sufficiently small definitions of "solve": http://arxiv.org/pdf/quant-ph/0502072v2

Definitions which turn out to be very small indeed.

Harder is an understatement =)

The bubbles don't solve Steiner Trees per se, they just give decent approximations. They are susceptible to local minimums. Scott Aaronson has given demonstrations against these claims.

Another one of those articles where they really should include a picture of the network the mold came up with. A picture really would say 1000's of words in this case; they spend the whole article describing what the mold did :-(

Arxiv has a paper by Andrew Adamatzky (one of the authors of the nytimes article) called "Are motorways rational from slime mould’s point of view?", from 13 Mar 2012, which has pictures:

http://arxiv.org/pdf/1203.2851.pdf

Take a look at page 4.

If we view slime molds as a sort of computing machine, which responds differently to different inputs, an intriguing angle is to use it for generative art, the way people use other computing formalisms like context-free grammars (http://www.contextfreeart.org), cellular automata, and other things.

The tricky thing is that slime mold tends to either die or gunk everything up if you aren't careful, but there are some artists "collaborating" with it in producing paintings, which makes for interesting outcomes sometimes because the mold seems to carry pigments around, and responds differently to different pigments and preparations of surfaces: http://slimoco.ning.com/

So what kind of algorithm does the slime mold use?

And what is the time complexity of its algorithm? Seems like you could measure it by using larger and larger problems and then determining whether the time increases exponentially.

That, to me seems like the most interesting problem. Kickstarter project anyone?

My naive guess is hill climbing based on chemical gradients. I have a strong hunch that large networks settle at local optimums.

I'd say more likely its equivalent to particle filters. Mold probably shoots spores all around the petri dish, and the spores that have better access to nutrients grow more, thus putting out larger proportion of spores in the next generation. A few generations later, all organisms that are either directly next to the nutrients, or next to another organism which has good access to nutrients survive.

My Tutor at university (Computer Science) is one of the leading experts on using Slime-Molds in computation. He makes robots controlled by them. Very interesting stuff I think, although biological computing isn't normally my area of interest.

Very interesting. I don't think slime-molds are fast enough to build a useful NP-oracle, though.

MST is polynomial, so you can't use it as an NP oracle, anyway.

And the fact that the slime molds didn't create the same layout every time implies they don't provide an optimum answer.

Not necessarily true. There could be multiple, equal-valued optima.

Exactly. Consider the case of all equal weights. In that case, every spanning tree is a MST. For the extreme cases (labeled complete graph, and a tree) of order n, those numbers are $n^{n-2}$ and 1, respectively, so the answer can be far from unique.

Next step : connect slime-mold to virtual reality , and expose API for it.

Reply on news.ycombinator.com