"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?


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.