Slashdot Mirror
Bacterial Computer Solves Hamiltonian Path Problem
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."
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.
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.
At best, this seems to be a novel form of analog computer. They have their uses, but calling them "faster than silicon" is very misleading; a soap bubble can solve the mean surface problem but I won't be replacing my Core 2 with one.
How can I believe you when you tell me what I don't want to hear?
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.
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.
Hmm. Deja vu here. DNA was used to solve this exact problem:
http://www.jyi.org/volumes/volume8/issue2/features/srivastava.html
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.
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.
Len Adleman did a more impressive DNA computing experiment way back in 1994. 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.