About bacteria solving NP-complete problems

[Reposted from jooray]

I post reaction to this article here.

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 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 from the point of genetic manipulation, I like that they contribute to the “standard biological components database”, but it has no direct implication for computational complexity.


Written by Juraj Bednár //