[schlomie]

Explanation of the problem: http://fold.it/portal/info/science#whygame

Protein structure prediction: As described above, knowing the structure of a protein is key to understanding how it works and to targeting it with drugs. A small proteins can consist of 100 amino acids, while some human proteins can be huge (1000 amino acids). The number of different ways even a small protein can fold is astronomical because there are so many degrees of freedom. Figuring out which of the many, many possible structures is the best one is regarded as one of the hardest problems in biology today and current methods take a lot of money and time, even for computers. Foldit attempts to predict the structure of a protein by taking advantage of humans' puzzle-solving intuitions and having people play competitively to fold the best proteins.

...

What shape will a protein fold into? Even though proteins are just a long chain of amino acids, they don't like to stay stretched out in a straight line. The protein folds up to make a compact blob, but as it does, it keeps some amino acids near the center of the blob, and others outside; and it keeps some pairs of amino acids close together and others far apart. Every kind of protein folds up into a very specific shape -- the same shape every time. Most proteins do this all by themselves, although some need extra help to fold into the right shape. The unique shape of a particular protein is the most stable state it can adopt. Picture a ball at the top of a hill -- the ball will always roll down to the bottom. If you try to put the ball back on top it will still roll down to the bottom of the hill because that is where it is most stable.

[InclinedPlane]

Protein folding is quite possibly an NP-complete problem. Determining the relative energy of a given protein-chain conformation can be done in polynomial time, it's a pretty simple problem. However, minimizing the energy is very difficult because there are so many degrees of freedom (on the order of the number of amino-acids in the protein).

[cousin_it]

You can build a machine that physically creates a specified protein and watches it fold. Will that qualify as a solver of NP-complete problems in polynomial time? Not likely! I'm pretty sure some proteins don't fold into their lowest possible energy configuration, they just find a local minimum. It's like computing minimum spanning trees with soap bubbles (there still exist cranks who think it works).

[asdkl234890]

Yet proteins fold in polynomial time in all living things.

[timr]

That's meaningless. They're not folding on a Turing machine, so "polynomial time" isn't defined.

[shiven]

Quite right! However, all we have are (imperfect?) versions of a Turing machine to solve the folding problem!

Maybe a Lisp machine would do better ;-)

At the end of the day, a linear sequence of amino acids has to end up in a three-dimensional conformation with short-range contacts being formed between atoms far away in the primary (linear) sequence. Add to this the complexity from long-range effects critical for the final structural stability and biological/biochemical function.

And don't even get me started on Intrinsically Disordered Proteins -- where, frankly, the future of the entire field lies !!!

[jbri]

Assuming this is an NP problem, then a nondeterministic turing machine is capable of solving it in polynomial time (by definition).

So it stands to reason that a properly-constructed quantum computer (being an approximation of a nondeterministic turing machine) would probably be able to solve the protein folding problem in polynomial time.

It's also not out of the bounds of possibility for similar quantum effects to explain how proteins fold the same way every time - an individual protein in fact being a superposition of all possible foldings, and the lowest-energy folding being the one that is actually observed whenever it interacts with anything.

[sid0]

There is no known way of getting a quantum computer to solve an NP-complete problem in polynomial time. Integer factoring is in NP but not complete for it.

[xyzzyz]

In order to talk about "polynomial time", you need to introduce some computational model. What computational model of living things do you have in mind?