NP Complete

An exerpt I found in mit opencourseware notes on NP-Complete problems in nature...

"1.2 In Nature

Nature deals with NP-complete problems constantly; is there anything we can learn from it? Biology employs what computer scientists know as genetic algorithms. Sometimes biology simply mutates the candidate solutions, but other times it combines them (which we call sexual reproduction).

Biology has adopted the sexual reproduction technique so widely that it must have something going for it, even if we don’t yet fully understand what it is. In experiments, local search algorithms that employ only mutations (i.e. “asexual reproduction”) consistently do better at solving NPcomplete problems than do algorithms that incorporate sex.

The best theory people currently have as to why nature relies so heavily on sex is that nature isn’t trying to solve a fixed problem; the constraints are always changing. For example, the features that were ideal for an organism living in the dinosaur age are different from the features that are ideal for modern-day organisms. This is still very much an open issue.

As another example of nature apparently solving NP-complete problems, let’s look at protein folding. Proteins are one of the basic building blocks of a cell. DNA gets converted into RNA, which gets converted into a protein, which is a chain of amino acids. We can think of that chain of amino acids as just encoded information. At some point, however, that information needs to be converted into a chemical that interacts with the body in some way. It does this by folding up into a molecule or other special shape that has the requisite chemical properties. The folding is done based on the amino acids in the chain, and it’s an extremely complicated process.

The key computational problem is the following: given a chain of amino acids, can you predict how it’s going to fold up? In principle, you could simulate all the low-level physics, but that’s computationally prohibitive. Biologists like to simplify the problem by saying that every folded state has potential energy, and the folding is designed to minimize that energy. For idealized versions of the problem, it’s possible to prove that finding a minimum-energy configuration is NPcomplete. But is every cell in our body really solving hard instances of NP-complete problems millions of times per second?

There is another explanation. Evolution wouldn’t select for proteins that are extremely hard to fold (e.g., such that any optimal folding must encode a proof of the Riemann Hypothesis). Instead, it would select for proteins whose folding problems are computationally easy, since those are the ones that will fold reliably into the desired configuration.

Note that when things go wrong, and the folding does get caught in a local optimum, you can have anomalies such as prions, which are the cause of Mad Cow Disease."

Pretty interesting stuff if you're into it...