= 27d567bc2d48d9f40e9ccc20ea370b15)
pengvado comments on Information theory and FOOM - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (93)
Why do you think nature can't solve NP-hard problems? When you dip a twisted wire with 3D structure into a dish of liquid soap and water, and pull it out and get a soap film, didn't it just solve an NP problem?
All of the bonds and atoms in a protein are "computing" simultaneously, so the fact that the problem is NP in terms of number of molecules isn't a problem. I don't understand BQP & so can't comment on that.
Incidentally, your observation about consistent folding is often right, but some proteins have functions that depending on them folding to different shapes under different conditions. Usually these shapes are similar. I don't know if any proteins routinely fold into 2 very-different shapes.
And there are at most N^2 of them, so that doesn't transform exponential into tractable. It's not even a Grover speedup (2^N -> 2^(N/2)), which we do know how to get out of a quantum computer.