Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
"DeepMind has predicted the structure of almost every protein so far catalogued by science, cracking one of the grand challenges of biology in just 18 months thanks to an artificial intelligence called AlphaFold", reads newscientist.com.
If protein folding is supposedly an NP-complete problem, does DeepMind deserve a millennium prize? What am I missing?
The $\mathsf{P}$ vs. $\mathsf{NP}$ problem asks whether $\mathsf{P}=\mathsf{NP}$. To settle this problem one needs to either provide a formal proof that $\mathsf{P}=\mathsf{NP}$ or a formal proof that $\mathsf{P}\neq\mathsf{NP}$.
One possible proof for $\mathsf{P}=\mathsf{NP}$ consists in exhibiting a polynomial-time algorithm that solves a $\mathsf{NP}$-hard problem (along with proving its correctness and that the algorithm's time complexity is indeed polynomial in the input's size). For an algorithm to solve a problem, it must return the correct answer on all possible input instances.
AlphaFold does not solve the protein folding problem in the formal sense, i.e., there is no guarantee that the returned solution is the optimal one (I'm not even sure if it works for arbitrarily large instances). It is merely a heuristic that provides good solutions to practical instances most of the time.
