Follow Slashdot stories on Twitter


Forgot your password?
Biotech Science

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."
This discussion has been archived. No new comments can be posted.

Bacterial Computer Solves Hamiltonian Path Problem

Comments Filter:
  • by rjh ( 40933 ) <> on Sunday July 26, 2009 @02:43AM (#28824879)

    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)

    by Bacon Bits ( 926911 ) on Sunday July 26, 2009 @03:52AM (#28825141)

    But it will solve the problem by "brute force", taking advantage of the massive parallelism inherent in the real world in the form of molecules or bacteria.

    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.

  • by kohaku ( 797652 ) on Sunday July 26, 2009 @05:19AM (#28825459)
    Why is the GP modded over the parent? "Simply another NP-complete problem" and "not a special case" are just wrong. As can be found on wikipedia, [] the following text states that solving one NP-complete problem faster means they are ALL solvable faster. Come on slashdot! Computational complexity 101!

    In computational complexity theory, the complexity class NP-complete (abbreviated NP-C or NPC, with NP standing for nondeterministic polynomial time) is a class of problems having two properties

    • Any given solution to the problem can be verified quickly (in polynomial time); the set of problems with this property is called NP.
    • If the problem can be solved quickly (in polynomial time), then so can every problem in NP.

    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.

  • by Atmchicago ( 555403 ) on Sunday July 26, 2009 @05:36AM (#28825521)

    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.


    Andrew Martens

  • Re:quantum computer (Score:1, Interesting)

    by Anonymous Coward on Sunday July 26, 2009 @07:19AM (#28825901)

    Not in polynomial time.
    It is conjectured that quantum computers can't solve NP-complete problems in polynomial time.

Genius is ten percent inspiration and fifty percent capital gains.