typodupeerror

## Bacterial Computer Solves Hamiltonian Path Problem135

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

• #### Summary is overrated (Score:5, Informative)

on Sunday July 26, 2009 @12:13AM (#28824505) Homepage
According to the abstract, the bacteria presently only solved the problem for a 3-node directed graph. Maybe someday it will be "faster than anything made from silicon", but... not right now.
• #### Re: (Score:1, Informative)

by Anonymous Coward

Also, the Hamiltonian path problem is not a special case of the traveling salesman problem, it is simply another NP-complete problem that is quite similar to the traveling salesman problem.

• #### Re: (Score:3, Funny)

by Anonymous Coward

It is a fucking special case of the fucking traveling salesman problem. Look, you fucking make a fucking edge of fucking infinite cost for any fucking edge not fucking present in the original fucking graph. Is the fucking shortest fucking tour finite? Fucking Christ on a fucking goddamn stick. Fuck!

• #### Re:Summary is overrated (Score:5, Funny)

on Sunday July 26, 2009 @01:14AM (#28824755)

the traveling salesmen I know did a lot of fucking on their routes. You must be correct.

• #### Re: (Score:3, Funny)

Oblig [xkcd.com]
• #### First bacterial computer virus? (Score:2)

Careful not to infect the bacterial brains with his STD's!
• #### Re: (Score:3, Interesting)

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, [wikipedia.org] 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 solutio
• #### Re: (Score:1)

That is how our brains work; however, I wouldn't use wikipedia to disprove anyone.
• #### Re: (Score:2)

Will it have fucking Buddanaise to fucking dip it into?

• #### Re: (Score:1)

Well, any problem in NPC is a "special case" of any other problem in NPC, up to polynomial reductions. That's what completeness means.
• #### Re: (Score:2)

The article is incorrect in stating that the Hamiltonian Path problem concerns finding the shortest path. This is not right. The HP problem simply asks whether or not a path exists that goes through every vertex exactly once. The TSP is concerned with finding the shortest *cycle* that goes through every vertex exactly once (except for the starting and ending vertex, which must be the same). If you want to be precise, TSP asks if there is a Hamiltonian Cycle that has length less than some constant k (since t
• #### Re: (Score:1)

Yeah, in theory they could scale this to more cities with more bacteria, but they'd probably have to build something like Mother Brain to scale to thousands... and "silicon" of course can currently handle that just fine.

Fine achievement though, despite the summary's smug sensationalism.
• #### Re:Summary is overrated (Score:4, Insightful)

on Sunday July 26, 2009 @03:14AM (#28825241)
Even worse, the colony does not even SOLVE the problem! If you let the bacteria grow enough, you have a pretty high probability of getting a solution. But no guarantee, because it's all probabilistic. If some of the bacteria happen to reach the correct solution, they turn the right color. Which is pretty easy to detect if you're just looking for a big patch of yellow bacteria, but not if there are millions of possibilities and only a few bacteria turned the specific color you are looking for. Sure, you could use resistance to antibiotics instead of colors, and kill off the bad solutions, but still, if no bacteria are left, that does not mean there's no solution. And since the number of possibilities grows exponentially with problem size, so will the required size of the bacterial colony. So forget about solving the HPP with 500 or so nodes. Then, on top of that, DNA is not exactly reliable. Already in this small and simple experiment, unexpected colors like pink etc. turned up.
• #### Re: (Score:1)

There are lots of interesting algorithms, that are probabilistic. The definition is, that if you run it long enough, the solution will be found.

Reliability is also backed up by the times you run experiment. You can easily discard pink colours, if you get yellow, you can check the result (remember, it's NP, so checking, if the answer is okay is deterministic polynomial, i. e. fast). So filtering out the wrong solutions is not a problem.

The principial problem is, that it does not scale well. You need to enume

• #### Re: (Score:1)

There are lots of interesting algorithms, that are probabilistic. The definition is, that if you run it long enough, the solution will be found.

Indeed, and such algorithms are widely used in practice, but they are not theoretically considered a "solution" because you might (in theory) have to wait forever to get a path, and you will never really be sure that no path exists (which is an important element of the Hamiltonian Path Problem). If a probabilistic algorithm is considered to be good enough, they should at least compare the bacteria against a computer running a probabilistic algorithm as well, and find that the computer is probably a lot fas

• #### Re: (Score:1)

Just use image analysis to find if there is any solutions. Something very simple like Gonzalez et al. [google.com.br]
• #### Re: (Score:2)

Even worse, the colony does not even SOLVE the problem! If you let the bacteria grow enough, you have a pretty high probability of getting a solution. But no guarantee, because it's all probabilistic.

To be fair, current computation is also essentially probabilistic. Solid state electronics like those based on transistors depend on statistical thermodynamic effects for their operation - it just turns out that the probability of a random fluctuation that causes unpredictable behaviour is small enough to be essentially zero - in principle with enough bacteria you could achieve similar levels of confidence.

The scale issue is a real one though, if your base unit is a bacterium instead of an electron you hav

• #### Re: (Score:1)

Well, what we should do is engineer a form that will eliminate heterogenous forms from the medium, and then allow them to propagate using the raw materials of their surroundings. At high enough levels the error factor will approach electron-level - say, if the medium were about the size of the surface of earth. Then we'd have enough computing power to answer some big fat np-complete problems, as long as the solution-set color can be interpreted from the color gray.

• #### Re: (Score:2)

The problem is, even the least green computer solving the problem wouldn't be characterized as an ecological disaster. Choose the bacteria carefully!

• #### Re: (Score:2)

Also, imagine using this method to solve a problem for which you didn't already know the solution. What exactly are the characteristics of the "correct answer"? Unknown.
In order to be useful, you must engineer a mapping of the possible solutions to genetics in a way where the solution is obvious without knowing what it will be beforehand. That sounds quite difficult. Maybe we could program some bacteria to find out how to do that.

• #### Re: (Score:1)

WTF - traveling salesman with three points, one of which is the start and one of which is the end - what paths are there to choose from?

• #### Re: (Score:1)

This sentiment seems awfully negative. It's progress, not some spectacular, worldchanging breakthrough. Not every scientist can emerge after 4 years in the desert with a nuclear bomb.

--
There are 10 types of people in the world: those who understand binary, and those who don't.
• #### Next up... (Score:2, Funny)

Foot fungus solves graph coloring!
• #### the possibilities! (Score:5, Insightful)

on Sunday July 26, 2009 @12:18AM (#28824533)
Wait, where's the advantage? OK so it's more efficient but can you run experiments over and over on the same hardware for a decade without repair? Is it scalable? I doubt it's feasible to have a Beowulf cluster of billion-dollar laboratories complete with post-grads to set up and write up reports analyzing each experiment. I'd like to see a schematic for a high-speed bacterial coupler before I start buying cycles on yogurt.
• #### Re: (Score:2, Insightful)

by Anonymous Coward

The advantage? Self-replication. Bacteria are crafted, made to do what they do naturally (replicate to populations of millions or more), and then create answers as a by-product of that replication. This has serious possibilities for streamlining any massive iterative function. Essentially, a biological computer grows to meet the problem at hand, unlike static circuits that must slowly work their way through a potentially massive set of answers. The technology isn't even in its infancy yet, but it's yet

• #### cue terminator joke in five, four, three... (Score:2, Funny)

by Anonymous Coward

The (bacterial computing) Funding Bill is passed. The (colony) goes on-line August 4th, (2017). Human decisions are removed from strategic defense. (The colony) begins to learn at a (exponential) rate. (They) become self-aware at 2:14 a.m. Eastern time, August 29th. In a panic, (humans) try to (feed them antibiotics.)

• #### Support Bacteria! (Score:1)

Support Bacteria! It's the only culture some people have!

by Anonymous Coward

I think this is quite misleading since the effort to genetically modify the bacteria is not included in the quantification of how fast the computation is being completed. If programmers are allowed to spend enough time to prepare input data for the fastest possible calculation, it may be just as fast or faster than the bacteria. Even if this is not the case, the overhead of preparing the bacteria should not be ignored.

• #### So? (Score:5, Insightful)

on Sunday July 26, 2009 @12:24AM (#28824567)

At best, this seems to be a novel form of analog computer. [wikipedia.org] They have their uses, but calling them "faster than silicon" is very misleading; a soap bubble can solve the mean surface problem [wikipedia.org] but I won't be replacing my Core 2 with one.

• #### Re:So? (Score:5, Informative)

<rjh@sixdemonbag.org> on Sunday July 26, 2009 @01:41AM (#28824867)
They can't. Soap bubbles can get misled by local minima just like naive hill-walking algorithms.
• #### Re: (Score:3, Insightful)

We don't know these bacteria can't be fooled, either. That's not the point, anyway: An analog computer may be useful. 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. It may solve the problem "quickly" in our perception, but it's far from efficient in polynomial time, and it doesn't help in terms of P = NP.

And like any analog computer, these bacteria need to be carefully designed to solve a specif

• #### Re: (Score:3, Interesting)

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 inh

• #### Re: (Score:2)

Electrical-silicon computers are *not* efficient. They're *not* smart. They're extremely stupid extremely quickly, and that's all.

They are neither "smart" or stupid. They are just machines that blithely follow instructions.

• #### Re: (Score:2)

Electrical-silicon computers are *not* efficient. They're *not* smart. They're extremely stupid extremely quickly, and that's all.

They are neither "smart" or stupid. They are just machines that blithely follow instructions.

... i.e. they are stupid.

• #### No, they are extremely efficient (Score:2)

That doesn't mean they are good at everything, but at what they ARE good at, they are exceedingly efficient. Digital computers are extremely efficient at crunching numbers. At their core, that is ALL they do, and they do it really, really well. Not only are they very quick at it, but they do it right, and they can show you their work. What I mean is that given a set of inputs, the produce a reliable set of outputs. You can also trace through all intermediate steps and watch the state at every step. They are

• #### Re: (Score:1)

So unless a way is found to make these analog computers capable of analyzing their own results and getting the one correct answer, they are a novelty more than anything else. Most people don't have labs full of grad students to sift through the results.

You clearly didn't RTFA. The bacteria do analyze their own result: Those with the correct solution glow yellow.

• #### Re: (Score:2)

May be they could replace our Slashdot editors instead?
• #### Hmm (Score:5, Funny)

on Sunday July 26, 2009 @12:39AM (#28824623)
So next time I itch it means the bacteria on my skin is trying to prove Fermat's last theorem ?
• #### Re: (Score:2, Funny)

Thank \$diety we're all slashdotters! The bacteria don't have to worry about skin being too narrow to contain.the truly marvellous proof!
• #### Re: (Score:2)

...I have discovered a truly marvellous proof of this, which this scrawny geek is too narrow to contain

• #### Re: (Score:1)

Trust thrush.
• #### Wonderful! (Score:3, Funny)

on Sunday July 26, 2009 @12:39AM (#28824625) Journal
So does this mean we're gonna have to re-educate the public and explain that they really can catch an infection from a computer virus? It wasn't that long ago that we were patiently explaining why that wasn't a concern.

Also, e. coli, really? I hope that, if this technology reaches the stage of commercial use, they've found something better. Or we're gonna hear a constant litany of people complaining that their computer is a piece of crap. It'll be worse than the "cat with a computer mouse" cartoons.* It will.

*Which is why I'm making the joke early and beating the rush.

• #### A-choo! (Score:5, Funny)

on Sunday July 26, 2009 @12:45AM (#28824641)

Aha!

• #### Ebola solves..... (Score:5, Funny)

on Sunday July 26, 2009 @12:54AM (#28824687) Homepage

the population problem.

• #### Re: (Score:2)

The three-body problem, as well.
• #### Bacteria Driven Computers? - Slant (Score:2)

Greg Bear wrote a book called Slant [amazon.com] that I read in the late 90's, featuring a biologically driven computer that met the claims of this experiment. While the reality is far from "faster than silicon", sci-fi has the fantasy covered.

• #### From what I hear (Score:1, Funny)

The hardware is really buggy.

*ducks*

• #### geez. (Score:1)

Talk about a computer virus. Norton Utilities now offering penicillin
• #### But... (Score:1, Redundant)

.. does it run Linux?
• #### this still does not prove p == np (Score:1)

You slashdot editors need to look up a bit of what has already been solved.... Soap can solve the Steiner problem. Soap, in water, acts as a surfactant, which decreases the surface tension of the water. This acts to minimize the surface energy of the liquid. This should minimize surface area (graph weight), and solve the problem. However, there is a problem with saying that P == NP because of this. Reducibility is the issue. If you can't reduce all problems in NP to this, you're sunk. The article doesn't
• #### Re: (Score:1, Insightful)

by Anonymous Coward

The reductions we already have work.

But this still doesn't say anything about P or NP, because those are defined with Turing machines, not soap bubbles.

• #### Re:this still does not prove p == np (Score:4, Interesting)

<rjh@sixdemonbag.org> on Sunday July 26, 2009 @01: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: (Score:2)

Absolutely- the soap film computers are comparable to effective heuristic algorithms for the Steiner tree problem, but they come with no proof that their solution is optimal. And there are examples where they are demonstrably incorrect (suboptimal in total length) some fraction of the time. There are plenty of quick algorithms for problems if you drop the requirement to be correct all of the time!

Nevertheless, playing with soapfilms and pegs can be interesting and a good illustration of some of the subtle

• #### My Computer Died (Score:4, Funny)

on Sunday July 26, 2009 @01:36AM (#28824855)
Now when you say that your computer died, you may be speaking literally...
• #### Good news for stinky nerds (Score:3, Funny)

on Sunday July 26, 2009 @01:42AM (#28824871)
So all that bacteria growing on those unhygienic D&D nerds is actually helping them with pathing, i knew they were cheating somehow, i could smell it...
• #### Re: (Score:2)

It gets worse. Right now, they won't allow calculators in math class. Soon, when you get caught blowing a booger and wiping it on the underside of your desk, you'll get accused of cheating.
• #### It has always been the case (Score:2)

Let us remember that the entire world was created from microscopic life forms, not by computers. The life forms learned from the environment and evolved in ways which even the most sophisticated computer would have an impossible time understanding. Let us remember that computers are, by a long shot, not the most efficient problem solvers. For instance, no computer can recognize patterns as well as a human being. The control system governing a hummingbird flight is way more advanced than that of the greatest

• #### Re: (Score:2)

Nature can only follow the laws of physics, which just so happen to be definable mathematically.

Hypothetically, all of this universe could be a simulation, running on some sort of computer. http://en.wikipedia.org/wiki/Simulated_reality/ [wikipedia.org] It's not something I personally subscribe to but I think that asserting some sort of fundemental divide between nature and math/computing is quite foolish.

• #### Turing complete? (Score:2, Funny)

Lets hype over it when it can run Linux

• #### Hamiltonian path != traveling salesman (Score:3, Insightful)

on Sunday July 26, 2009 @02:01AM (#28824945)
TFA oversimplifies by claiming that finding a Hamiltonian path solves the traveling salesman problem of finding the shortest path. The traveling salesman problem deals with variable edge lengths instead of just finite/infinte, and therefore requires a bit more complex implementation to solve (although they are both still NP-complete).

I would be more impressed if they found the shortest path on an undirected graph with variable length edges.
• #### Re: (Score:3, Informative)

Well, Since both the Hamilton path problem and the traveling salesman problem are NP-complete, there exists a polynomial time reduction of one problem into the other. So if you could solve the Hamilton path problem efficiently, and wanted to solve an instance of the traveling salesman problem (or the satisfiability problem, or the integer programming problem, or the partition problem, or whatever other NP-complete problem you might imagine), all you'd have to do is use the polynomial-time reduction to conv

• #### Re: (Score:2)

I didn't RTFA, and the other comments in the discussion make me skeptical anyway, but your post seems to contradict itself. If the Traveling Salesman Problem is NP-complete (which I know to be true) and the Hamiltonian Path Problem is also NP-complete (which I assume is true from this discussion), then solving one problem is isomorphic to solving the other and a solution to either can be transformed into a solution to the other in polynomial time. If you'd be impressed "if they found the shortest path on

• #### parallel computations only half the battle (Score:4, Insightful)

on Sunday July 26, 2009 @02:20AM (#28825035)

Hmm. Deja vu here. DNA was used to solve this exact problem:

It should be noted, however, that even though the DNA would be able to compute the routes in a massively parallel fashion, you still would have to search all the solutions to identify the shortest one, so that kind of defeats the purpose of it. Unless the DNA or the bacteria could compute all the results _and_ identify the correct and optimal answer, then as far as we are concerned the problem is still gotta be close to NP complete (IE strands of DNA to check go up exponentially with problem size). Sounds like these bacteria change color, so maybe that helps reduce the size of the answer set.

• #### Re:parallel computations only half the battle (Score:5, Interesting)

on Sunday July 26, 2009 @04:36AM (#28825521) Homepage

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: (Score:1, Insightful)

by Anonymous Coward

Now I remember why I still read slashdot. Despite all the "frist post", "hot grits", "in soviet russia", "goatse" and whatever other random bollocks goes on here, you still get real geeks, making real news, posting real insightful comments.

Thanks Andrew for taking the time to read and post here..

It sounds like incredibly interesting work, particularly so for me as a software engineer with a wife who works in the biomed industry. Congrats on the paper!

Also, with reference to the gp post, I thought that the

• #### Re: (Score:2)

Awesome to have you post this, Andrew. Actually I'm a bit embarrassed since I'm a typical ignorant slashdotter who only read the guardian summary article and not much of the paper itself--never expected to draw the attention of someone who actually knows what they are talking about, someone who was one of the original investigators!

In response to another poster who raised an eyebrow at my phrase "deja vu" I really meant that this article and experiment reminded me of the previous DNA experiment, which of c

• #### Re: (Score:1)

As I wrote, it still does not solve the mass of DNA required to enumerate all solution. It should be however noted, that a good solution of this particular problem is important, because as it's NP-complete, all other NP problems could be solved with cca the same complexity.

So this is a good problem, because it can be easily represented in DNA sequences and if solved, any NP algorithm could be solved using the machine solving this problem.

• #### Re: (Score:1)

Deja vu?
Not quite, they cite his paper in the references and acknowledge Adleman's work as "seminal" (pp. 4-5). But where he used PCR to replicate DNA fragments (where nucleotides coded for data of the mathematical problem instead of actual amino acids), they use a living organism - the E. coli bacteria.
The problem they claim to solve is the Hamiltonian path problem, so I'm not sure what you mean by "identify the shortest one". But clearly they left the problem of false positives out for a later study.
• #### Bacteria doing math? (Score:1)

Are they getting that hard up for grants? What is it, flagellate for a one, don't flagellate for a zero? Everybody get in line so we can read the binary?
• #### One last math problem? (Score:2)

Wait. E.coli? As in a Escherichia The Killer Diarrhea Coli? Millions and millions and millions of reproducing E.coli bacteria? Not on my desk, thank you very much.

• #### Re: (Score:1)

Wait. E.coli? As in a Escherichia The Killer Diarrhea Coli? Millions and millions and millions of reproducing E.coli bacteria? Not on my desk, thank you very much.

I've got bad news for you: You already have millions and millions and millions of reproducing E.coli bacteria in your colon.

• #### Re:One last math problem? (Score:4, Informative)

on Sunday July 26, 2009 @05:04AM (#28825657)

E.coli his a very common bacterium with a large family of strains, only a few of which are particularly dangerous to a healthy human (and few more are harmful only to people who are in not-so-good good condition such as the elderly or people with serious illness particularly those with an immune system targeting disease or those weakened by chemotherapy).

Get ready to panic: you almost certainly have a couple of strains of e.coli throughout your intestine right now. Everyone does. As do most warm-blooded animals. It really is that common and generally harmless.

The strain you are presumably most concerned about, as it is one that has hit the headlines a number of times in the last decade or so, is O157:H7 which is a common agent in food poisoning outbreaks. 157/7 is a nasty bugger, and a hardy one too, but I doubt the researchers in this story are using it when there are so many much less troublesome varieties to play with.

E.coli is often use in research like this because its genetics relatively simple and so it is relatively well understood, meaning it is more predictable so experiments are less likely to misfire in surprising ways. It is also comparatively stable (unlike some bacteria and other organisms that mutate every second sneeze). I very much doubt they are working with a strain that is in any way dangerous to a human, and E.coli is not transmitted by air so even if some of the cells in a bacterial computer mutate into a more deadly type they are not going to harm you unless you eat the thing directly or your food comes into contact with it.

• #### Re: (Score:2)

... E.coli is not transmitted by air so even if some of the cells in a bacterial computer mutate into a more deadly type they are not going to harm you unless you eat the thing directly or your food comes into contact with it.

So... no food allowed in the computer center. :(

• #### quantum computer (Score:2)

Could a quantum computer be used to solve this?

• #### Re: (Score:1)

Since a quantum computer can solve everything a classical computer can, of course a quantum computer can solve it (provided you manage to build one, of course).
However, the real question is: Can a quantum computer be used to solve it efficiently? Well, it's generally assumed that quantum computers cannot efficiently solve NP-complete problems (there's no proof, but then there's no proof for classical computers either).

• #### Re: (Score:1, Interesting)

by Anonymous Coward

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

• #### Count the mass of DNA! (Score:1)

This is not that important as it sounds. It would not be able to solve NP-complete problems for large inputs, because it enumerates all possibilities in DNA base-pair combinations. This has actually been done before with pure DNA and their manipulation (now they use bacteria for color-marking and thus selection of the right solution's DNA sequence).

Anyways, this does not scale well, having only a few hundred cities would require DNA, that would weight cca the mass of our earth.

So this result is nice as a ge

• #### I Thought... (Score:1)

Willy Loman solved this problem years ago.
---
Free The Mouse
• #### Science Marches On (Score:2)

So now a dose of clap is better at math than the hooker that gave it to me. Or me, for that matter. Now I feel REALLY pathetic.

• #### A use for keyboard crumbs after all (Score:2)

OK, so if I translate this correctly I may actually be typing on the most powerful part of my PC?

Thank God they didn't base this on swine flu - it's going at a rate as it is .. :-)

• #### Where is PETA on this? (Score:1)

PETA already objects to using bacteria to clean up oil spills... what do they think about using bacteria to do math?

• #### This is incredibly underwhelming (Score:3, Insightful)

on Sunday July 26, 2009 @07:31AM (#28826157)
Len Adleman did a more impressive DNA computing experiment way back in 1994 [wikipedia.org]. Since then Adleman has stated that DNA computing is a dead end until someone comes up with a huge breakthrough. Well...it would be a huge understatement to say that this E. Coli experiment isn't a breakthrough.
• #### Meh. (Score:2)

And i thought this had something to do with the Hamiltonian Principle. Turns out it's only CS.
• #### Hex, is that you? (Score:2)

Once again, life imitating art: http://en.wikipedia.org/wiki/Hex_(Discworld) [wikipedia.org]
• #### Cool, but not useful (Score:2)

First, this is pretty cool. Enough said about that.

Unfortunately, I don't think this will be useful for solving NP-complete problems. For those of you who don't know much about algorithms, NP-complete problems are hard to solve because they become much harder as you make the problem "bigger". It is perfectly possible for problems to be solvable in a reasonable amount of time for small problem sizes, like n=3 that the authors of this article solved.

The paper explains that because bacteria can multiply exp

• #### My gut tells me... (Score:1)

... this could be the Next Big Thing, or a fart in the wind...
• #### Can a bacterial computer ... (Score:2)

On second thought ..... Eeewwww!! That would be pretty nasty looking p0rn.

• #### One thing is that your computer can infect you (Score:1)

Much more annoying is the fact that you will start flashing once the infection finds the answer!
• #### The Irony of It All (Score:1)

Keyboards are supposed to have more bacteria than a toilet seat. That means every time I start typing a program I have destroyed the solution to one of life's great problems. My keyboard solves problems I couldn't possibly program solutions too!!

I guess I should just retire and each day take a picture of my keyboard to save the current solution to a problem, then piss on it to erase the current solution and start the new program running. I guess if it is not to complex a problem, I can take a picture of my