> Isn’t solving protein folding np-complete? I'm not an expert on protein folding, but if you refer to this paper [1], it only claims that one particular optim

> Isn’t solving protein folding np-complete? I'm not an expert on protein folding, but if you refer 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 it is not proven that protein folding is hard (in terms of computational complexity theory), although it does seem likely. > How did this new algo get past that? This is a very frequent and legitimate question due to the widespread misconception that "large NP-hard problems cannot be solved". Maybe it does not help that the term "intractable" is often used as a synonym for "not in P", while that word has obvious connotations outside of complexity theory. To the contrary, for some specific types of NP-hard problems, gigantic instances are routinely solved in a matter of minutes. Prominent examples are knapsack problems, SAT problems [2], and the Traveling Salesman Problem [3] or more generally Mixed Integer Programming [4]. To give you some intuition: yes, the complexity still grows exponentially with the size of the problem, but if the constant factor is really tiny, we may still be able to tackle fairly large instances. > Did it solve p=np too? Definitely not. For that, again, we would need, some formal statement that protein folding as solved there is NP-hard (this seems feasible, but I don't know that it has been done). Then, more importantly, we would need a theoretical result showing that the proposed solution method is of polynomial-time complexity -- being able to solve individual instances "quickly" is nice but not entirely relevant to the theoretical complexity side of things. [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