I thought protein folding was harder than NP. IIRC, calculating the free energy of a molecule is in #P (count the number of solutions to a problem in NP), and

I thought protein folding was harder than NP. IIRC, calculating the free energy of a molecule is in #P (count the number of solutions to a problem in NP), and you still need to step it through time or otherwise deal with the actual folding bit. I might be remembering incorrectly though. Edit: http://en.wikipedia.org/wiki/Sharp-P-complete http://en.wikipedia.org/wiki/Sharp-P-complete Also: whoops - looks like structure prediction can be done with high accuracy in NP - just don't try to animate it :)