Ask HN: How did the protein folding algo get past complexity?
Isn’t solving protein folding np-complete? How did this new algo get past that? Did it solve p=np too?
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