Re:AlphaFold: a solution to a 50-year-old grand challenge in...
by glatteis on Monday November 30, 2020 @11:26AM
(#25255460)
> But wasn't protein folding supposed to be NP-hard?
Yeah, at least some variations of it are NP-hard. SAT is THE NP-complete problem, but there are some really good SAT solvers around. This basically means: They have a solution that mostly does very well on most instances. But because (probably) P != NP, you will never have a polynomial time algorithm for this.
Yeah, at least some variations of it are NP-hard. SAT is THE NP-complete problem, but there are some really good SAT solvers around. This basically means: They have a solution that mostly does very well on most instances. But because (probably) P != NP, you will never have a polynomial time algorithm for this.