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."
Summary is overrated (Score:5, Informative)
Re:Summary is overrated (Score:1, Informative)
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:So? (Score:5, Informative)
Re:Hamiltonian path != traveling salesman (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 convert the source problem instance you wanted to solve into the equivalent Hamilton path problem, and apply the reduction in reverse on the answers to get the answers you wanted for the problem you wanted to solve.
Re:One last math problem? (Score:4, Informative)
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.