Bacterial Computer Solves Hamiltonian Path Problem 135
Rob writes "A team of US scientists has engineered bacteria that can solve complex mathematical problems faster than anything made from silicon. The research, published today in the Journal of Biological Engineering (abstract and provisional PDF), proves that bacteria can be used to solve a puzzle known as the Hamiltonian Path Problem, a special case of the traveling salesman problem. The researchers say that this proof-of-concept experiment demonstrates that bacterial computing is a new way to address NP-complete problems using the inherent advantages of genetic systems."
Re:this still does not prove p == np (Score:4, Interesting)
Soap bubbles can be misled by local minima just like hill-walking algorithms. The problem with soap bubble computation is that when it hits a stable state -- how do you know it's stable? For all you know it's going to collapse further in a few seconds.
Repeat after me: the "soap bubbles can solve the smallest surface problem" meme is wrong as a matter of physics, and wrong as a matter of computer science.
Re:So? (Score:3, Interesting)
If you've ever looked at a diagram of how a CPU implements DIV or MUL for floating point numbers, then you wouldn't think that the brute force approach would necessarily be so bad. Take a look at size, scale, and cost of ENIAC and then come tell me a Petri dish is "slow and inefficient". Silicon takes advantage of massive speed of serial operations inherent in electron flow and the basic ability to electrically flip switches. Electrical-silicon computers are *not* efficient. They're *not* smart. They're extremely stupid extremely quickly, and that's all.
Re:Summary is overrated (Score:3, Interesting)
Anyway, this article is about solving the problem in parallel with bacteria (which is totally cool, don't get me wrong.) It's not a faster algorithm, although I suppose you could argue that massively parallelizing it IS a faster solution.
Re:parallel computations only half the battle (Score:5, Interesting)
I'm one of the co-authors of the paper. Indeed, we were aware of what Adleman had done, and were partly inspired by his idea. However, his method required much more manual labor to do the computing, whereas once we have assembled our genetic sequences, we let the bacteria do the thinking.
The color changes were used to identify those bacteria which found a solution. Ideally other selective markers would also work, such as antibiotic resistance. The big issue is that our system can yield false positives, so depending on your setup some manual checking is required.
The Guardian article is rather misleading and inaccurate. We never had the intention of replacing your desktop PC, nor do we claim that our 3-node implementation is faster than a computer (in fact, someone spending 10 minutes or less can figure out a 3-node problem). I'm more excited about the proof-of-concept: we can encode a mathematical problem by using a molecule, hand it to a living organism, and get a correct output. The work was also done by undergraduate students in under a year. We presented our work at iGEM 2007, for those interested.
Cheers,
Andrew Martens
Re:quantum computer (Score:1, Interesting)
Not in polynomial time.
It is conjectured that quantum computers can't solve NP-complete problems in polynomial time.