Hacker News Reader

Comment by dhs | Hacker News Reader

Protein folding is suspected to be an NP-complete problem <http://www.liebertonline.com/doi/abs/10.1089/cmb.1998.5.27 >, so it seems to me that having reason to believe it will someday be solved equals having reason to believe that someday NP-complete problems can be computed in polynomial time. Alternatively, you might hope for a domain-specific approximative algorithm, but this seems tricky, too, since mis-folded proteins can end up as really bad stuff, e.g. prions <http://en.wikipedia.org/wiki/Prion >.

View on HN

Saying it's NP-complete doesn't prove we can't solve it well enough for simulation. As a physical problem become "pathologically NP", Nature becomes non-deterministic too; it seems unlikely that Nature will make extensive use of a protein that doesn't reliably fold in a certain way, or some small constrained set of ways.

See http://www.scottaaronson.com/papers/npcomplete.pdf

Not that I wouldn't like to be as optimistic, too, but Nature does seem to have made enough use of unreliably folding proteins to have come up with BSE, Parkinson's disease, and some others <http://en.wikipedia.org/wiki/Protein_folding#Incorrect_prote... >.

I'm a big fan of Scott Aaronson, too, btw :-) Here's a pic of him demoing the soap bubbles experiment he refers to in that paper you linked to <http://www.scottaaronson.com/soapbubble.jpg >.

I thought of mentioning that, actually, but figured it would be extraneous. However, if they are all indeed pathological then perhaps we can do our simulated humans a favor and not simulate the pathological path.

Still, as discussed in another comment I made, I seriously, seriously doubt that we will ever simulate any sort of intelligence by raw physical simulation. It just isn't feasible with any realistic computational technique.

The article says that the HP model is NP-complete. But water folds protein very quickly. I may be misunderstanding things here, but if protein folding (as opposed to a particular model of protein folding) is NP-complete, shouldn't it be slow in real life too?

I recall reading an interview with someone who founded a company that builds computers for simulating biological systems in silico who thought that there were much better algorithms waiting to be discovered because nature can do it quickly. I can't find it now.

Reply on news.ycombinator.com