I’ve heard that solving these problems could help solve cancer specifically through protein folding problems but I have no idea how.
In: Biology
So the thing which makes NP(C) problems interesting is that they are hard to compute, but easy to verify.
For example a sudoku has pretty simple rules, and you can verify that no digit occurs twice in the same row/column/box more than once pretty easily. To solve it however there is always some guessing, seeing where it gets you, and reverting when it is false. That’s why the N in NP stands for non-deterministic.
With protein folding it’s pretty similar: a long chain molecule can fold in many different shapes which each their own behavior. It’s easy to verify from a functional “fold” whether it’s a valid protein, but hard to generate functional folds from the protein.
Finding better solutions for NP problems, allows us to more easily find functional folds for the proteins in our body, and allow us to fold the proteins ourselves into those shapes to get desired behavior. Now we mostly have to guess and see what it gives.
Latest Answers