[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?