3 ms·

the thing to remember about P vs NP is that you can solve NP problems very quickly, but it takes NP time to verify that the solution is correct. I think you ha

by jdale27 17y ago

the thing to remember about P vs NP is that you can solve NP problems very quickly, but it takes NP time to verify that the solution is correct. I think you have it backwards. A problem is in NP if the solution can be verified in (deterministic) polynomial time. But (as far as we know) finding the solution may take much longer. For example, the statement of TSP as a decision problem is: "Given these distances between the cities, is there a closed tour of length less than K?" If someone hands you a proposed solution -- a list of the cities, in the order you should visit them -- it is easy to (a) verify that the list contains all cities, and (b) the length of the tour is less than the required K. That is why TSP is in NP. I didn't really follow the rest of your comment, so I'm not sure what bearing this has on your ideas on protein folding.

jballanc 17y ago
I may have my terminology backward. (I am a computational biologist, not a mathematician.) I think we're saying the same thing, though. Given that a protein folds to a particular conformation (3-D arrangement of atoms in space), you should be able to verify that a specific folding pathway is valid for getting there. However, without knowing ahead of time what the folded conformation is, determining the lowest energy conformation would require trying all possible conformations. So, yeah, I think I've got the terminology backward, but the point remains. Nature can solve protein folding very quickly (depends on kinetics), but to know whether the fold is the best (depends on thermodynamics) requires trying all possible folds.
- jdale27 17y ago
  determining the lowest energy conformation would require trying all possible conformations I apologize if it seems like I'm arguing over semantics, but from the computer science perspective, solving the protein folding problem (as opposed to approximating it) means finding an algorithm that does give the lowest energy conformation, without (in order for it to be tractable) trying all conformations. In some formulation of protein folding that is NP-complete, your statement (require[s] trying all possible conformations) is tantamount to P!=NP. So I'm guessing you don't have a proof of that. ;) I admit that this is weak reasoning, but consider an analogy from computational biology: the Needleman-Wunsch algorithm for finding the optimal global alignment between two sequences. There are exponentially many possible alignments. Through the magic of dynamic programming, Needleman-Wunsch guarantees us the optimal alignment without trying all of them (it works in polynomial time). We can't rule out the possibility that some similarly clever algorithm can do the same for protein folding. Now, Needleman-Wunsch works with respect to a scoring function that happens to make the problem tractable. In the case of protein folding, we'd have to ensure that the energy function we're optimizing with whatever clever algorithm we come up with is close enough to reality for the results to be useful to biologists.
  - jballanc 17y ago
    No need to worry about arguing semantics, I'm learning here. As I've said, I'm what you'd call an applied computer scientist. While I've got a good handle on tractability, dynamic programming, and the like, sometimes I miss the formalisms of the terminology. In some formulation of protein folding that is NP-complete, your statement (require[s] trying all possible conformations) is tantamount to P!=NP. So I'm guessing you don't have a proof of that. ;) Haha, ok, yes. You've got me there. Actually, that also clears up a few issues I was having with the original article. I tend to confound tractability and NP-complete. If I follow you now, an algorithm that can fold a protein to lowest energy is the solution. If that solution can be shown to be correct without trying all possible conformations, then it is P. If the only way to verify it correct would be to explore all fold space, then it would be NP and and P!=NP. In other words, my original assertion that protein folding is not, strictly speaking, NP relates to the fact that nature does not try all possible conformations. We could write an NP solution that does, but this is not what happens in reality. So, either nature is solving a slightly different problem (it doesn't worry about finding the global energy minimum exactly), or P=NP and the "algorithm" (in this sense a combination of physical laws) used by nature solves the same problem as our NP search of all conformation space.

by jdale27 17y ago

jballanc 17y ago

I may have my terminology backward. (I am a computational biologist, not a mathematician.) I think we're saying the same thing, though. Given that a protein folds to a particular conformation (3-D arrangement of atoms in space), you should be able to verify that a specific folding pathway is valid for getting there. However, without knowing ahead of time what the folded conformation is, determining the lowest energy conformation would require trying all possible conformations. So, yeah, I think I've got the terminology backward, but the point remains. Nature can solve protein folding very quickly (depends on kinetics), but to know whether the fold is the best (depends on thermodynamics) requires trying all possible folds.

jdale27 17y ago
determining the lowest energy conformation would require trying all possible conformations I apologize if it seems like I'm arguing over semantics, but from the computer science perspective, solving the protein folding problem (as opposed to approximating it) means finding an algorithm that does give the lowest energy conformation, without (in order for it to be tractable) trying all conformations. In some formulation of protein folding that is NP-complete, your statement (require[s] trying all possible conformations) is tantamount to P!=NP. So I'm guessing you don't have a proof of that. ;) I admit that this is weak reasoning, but consider an analogy from computational biology: the Needleman-Wunsch algorithm for finding the optimal global alignment between two sequences. There are exponentially many possible alignments. Through the magic of dynamic programming, Needleman-Wunsch guarantees us the optimal alignment without trying all of them (it works in polynomial time). We can't rule out the possibility that some similarly clever algorithm can do the same for protein folding. Now, Needleman-Wunsch works with respect to a scoring function that happens to make the problem tractable. In the case of protein folding, we'd have to ensure that the energy function we're optimizing with whatever clever algorithm we come up with is close enough to reality for the results to be useful to biologists.
- jballanc 17y ago
  No need to worry about arguing semantics, I'm learning here. As I've said, I'm what you'd call an applied computer scientist. While I've got a good handle on tractability, dynamic programming, and the like, sometimes I miss the formalisms of the terminology. In some formulation of protein folding that is NP-complete, your statement (require[s] trying all possible conformations) is tantamount to P!=NP. So I'm guessing you don't have a proof of that. ;) Haha, ok, yes. You've got me there. Actually, that also clears up a few issues I was having with the original article. I tend to confound tractability and NP-complete. If I follow you now, an algorithm that can fold a protein to lowest energy is the solution. If that solution can be shown to be correct without trying all possible conformations, then it is P. If the only way to verify it correct would be to explore all fold space, then it would be NP and and P!=NP. In other words, my original assertion that protein folding is not, strictly speaking, NP relates to the fact that nature does not try all possible conformations. We could write an NP solution that does, but this is not what happens in reality. So, either nature is solving a slightly different problem (it doesn't worry about finding the global energy minimum exactly), or P=NP and the "algorithm" (in this sense a combination of physical laws) used by nature solves the same problem as our NP search of all conformation space.