Slime mould mashup models fiendish computing problem

A pair of English researchers have offered up a “virtual slime mould” as a technique for one of mathematics' – and computer science's – classic problems, the travelling salesman problem. In the travelling salesman problem, the challenge is to find the shortest possible route that includes a given set of locations or cities: as …

This topic is closed for new posts.

"it becomes increasingly difficult to test a solution in polynomial time (that is, the travelling salesman problem is NP-hard)"

Hmm... I actually had to look this up, getting alzheimerish and all, but it is immediately clear that this is not a good definition.

NP-hard means that the problem is "at least as hard as" (and probably harder than) a problem in NP-complete.

How hard is that? Simples:

NP-complete problems are those problems which are easy to check if you are given a solution. "Easy to check" means there is a Turing Machine which can verify that a purported solution actually is a solution in polynomial time of the input size. This is the "P" of "NP".

However, getting a solution may be difficult. Generally you need to search through a large space, moving back and forth through it. If you have a super-parallel (exponentially large or more) Turing Machine that can run all the possible searches through the space simultaneously, and then verify each solution in polynomial time (as described above under "P") and then just print to the common tape if a correct solution was found (if it exists), then you can relax as you just need polynomial time to solve the problem overall. This is the "N" of "NP"

Actual Turing Machines do not have the luxury of being exponentially (or better) parallel, and thus reality imposes that you wait a long time (exponentially or worse) for the solution to your NP-complete problem.

Now, the NP-hard problems are even more difficult (in terms of number of operations till solution) than the ones that can be solved by the magic machine described above, so they sure are harrrd.

I also recommend that interested readers check NP-complete Problems and Physical Reality if they haven't yet done so. It's pretty eye-opening.

Can NP-complete problems be solved efficiently in the physical universe? I survey proposals including soap bubbles, protein folding, quantum computing, quantum advice, quantum adiabatic algorithms, quantum-mechanical nonlinearities, hidden variables, relativistic time dilation, analog computing, Malament-Hogarth spacetimes, quantum gravity, closed timelike curves, and "anthropic computing." The section on soap bubbles even includes some "experimental" results. While I do not believe that any of the proposals will let us solve NP-complete problems efficiently, I argue that by studying them, we can learn something not only about computation but also about physics.

I did my own version of this once...

Except I substituted the salesman/slime mould for Paris and nightclubs with VIP lounges with "seedy reputations" in a large world class capital city, represented the cities that needed visiting! It worked a treat and we got some good results, though it cost a fortune in chauffeur driven limos and we needed to have a "clean-up crew" on standby at all times!

So what we need ..

.. is a massive glob os slime to drop salesmen in?

Cool. May I do the dropping? :)

Myxop

The article missed a mycological opportunity by not even once referring to the slimies by their more colourful name of myxomycetes.

Biological problem solvers

Now I like ant colony solutions and I like slime growth solutions, but which is better?

There's only way to find out... FIGHT!

(Seriously, no Harry Hill icon...?!)

Ware tetrology comes true!

So Rudy Rucker's mouldies turn out to have come "true". This makes me very happy.

This post has been deleted by its author

Old farts might perhaps remember...

Gordon Pask's "fungal computing" from the 1950s.

All the best,

John.

This topic is closed for new posts.