> (it's NP-complete after all) Protein folding is a physical/biological phenomenon. AFAIK we don't currently have a proper exact mathematical formulation of th

> (it's NP-complete after all) Protein folding is a physical/biological phenomenon. AFAIK we don't currently have a proper exact mathematical formulation of the problem that would let one determine its complexity. You may be referring to this paper [1]. It only claims that one particular optimization problem, believed to give a solution to protein folding problems, is NP-hard. So, even if a suitable exact formulation exists, it is not yet proven that protein folding is hard, although it for sure seems plausible. By the way, it is perfectly possible today to solve some very large-scale NP-hard problems (think millions of variables and constraints) in reasonable amounts of time (think minutes or hours). Examples are knapsack problems, SAT problems [2], the Traveling Salesman Problem [3] or more generally Mixed Integer Programming [4]. [1] "Complexity of protein folding", 1993, by Aviezri S. Fraenkel [2] http://www.satcompetition.org http://www.satcompetition.org [3] http://www.math.uwaterloo.ca/tsp/ http://www.math.uwaterloo.ca/tsp/ [4] http://plato.asu.edu/bench.html http://plato.asu.edu/bench.html