Originally posted by plaidfishes
The statistical prediction of protein folds is a problem that many suspect to be NP-complete. In plain english, "The problem is impossible to solve".
Well, not impossible, just REALLY REALLY HARD. If statistical prediction is indeed NP-complete, then it can't be done in better than exponential time, by any algorithm known. This of course doesn't mean it can't be done, just that no one knows how. The interesting thing about NP-completeness is that if you find a way to do any (truly) NP-complete problem in polynomial time, then because of some properties of NP-completeness (that I don't know, I just know about), you will be able to solve every NP-complete problem in polynomial time.

Which means, if statistical prediction is in fact NP-complete, and Howard found a way to do it in logarithmic time (which is actually better than polynomial)...