The Status of the P Versus NP Problem
cacm.acm.org
cacm.acm.org
http://blog.computationalcomplexity.org/
I am not in TCS, but I do enjoy what bits and pieces are understandable to me.
(For those who are more familiar with the topic, I am generalizing. I'd love to debate Protein Folding != NP though...maybe in a different forum?)
Now while there are some proteins that will unfold and then fold correctly again, most can't do that. Most don't start out as one long chain that then crumples in the right shape on its own. Most are carefully built from other parts, carefully guided along the desired path of entropy. And if they misfold, and that does happen, they are taken out.
Now I personally have always thought of it as a simulation. Think about a can of mixed nuts. Have you ever noticed that the biggest kinds are always on top, and the smallest at the bottom?
You might have to shake the can for a while but they will sort by size with the biggest on top. This is a function of friction and volume. If you shake a glass jar of mixed nuts, you can almost see a flow along the sides with the smaller ones flowing down and the bigger ones "floating" to the top.
Imagine you were given the starting position of each nut, and the exact time and direction and force of the shaking of the jar. You are asked to write a simulation which will predict the final locations of each nut.
If you think about a single threaded algorithm looking at each nut and how it nudges its neighbor and its neighbor and so on, it's a lot of calculations.
But if you think of it a multi-threaded simulation then things get interesting.
It also triggered one of those 'holy crap I have so much to learn' moments, followed shortly by a 'what the hell am I doing wasting my time with all these silly things I do' moment. ;)
Proteins have too many atoms for even these techniques to be efficient. Now we're getting out of my area. As I understand it researchers do a Monte Carlo search of all possible configurations of amino acids(or even protein segments). Naively searching the space of all configurations would be make this NP. Of course you don't have to search the entire space. You can limit each step to make small changes only from an initial configuration and stay along a Markov chain of probable intermediate steps. I don't know enough to say that this would always be solvable in polynomial time, and of course you could miss the true minimum answer.
I'd love to hear from someone who knows more.
What I'm trying to get at is wondering if nature uses very good heuristic/approximate/probabilistic algorithm. I.e. if there is an algorithm that almost always works and having a few proteins that aren't at global minima isn't an issue and they dissipate very quickly, then observation would make it look like nature is solving the problem exactly even if its not.
Alternatively, the proteins we find in nature might be more tractable than the general problem described in all its mathematical glory (i.e. the inputs might be restricted to some subset of the input space which is solvable very quickly).
That depends on the thermodynamics. Specifically, it depends on the depth of the local minimum and the energy in the system. With some random chance, a protein can get out of a local minimum and fold into a different conformation. If nature is depending on the fold not changing, this could be a problem.
What sorts of problems? Would you need a lot of "bad" proteins to cause problems or just a few?
Again, it depends. In general, unfolded proteins are a bad thing. They are also a fairly common thing to find in cells, and cells have a specific "unfolded protein response" that kicks into gear if there are too many. Too many unfolded proteins literally "gum up the works".
For prions, tau (in Alzheimer's), and others, the story is a bit different. In these cases, the presence of even a few improperly folded proteins can catalyze further misfolding.
Alternatively, the proteins we find in nature might be more tractable than the general problem described in all its mathematical glory
This is almost certainly the case, but more tractable != not intractable. Solving the problem also requires clever solutions and a better understanding of physics. If your curious, I did my Ph.D. preliminary exam on one example (modern methods of handling side-chain entropy, including belief propagation techniques). The LaTeX source is at: http://github.com/jballanc/prelim/
Interesting. You mean totally unfolded or not folded correctly (i.e. proteins that haven't started the process or proteins that went through it and got to the wrong state)?
Also, does this mean that "nature has solved this problem" aren't true? I.e. "nature" doesn't get it right all the time, just often enough that we're generally okay?
In biology, there's little difference between "totally unfolded" and "not folded correctly". (In fact, there's been some research indicating that there may not be such a thing as "totally unfolded"; i.e. that all proteins have some structure all the time.) There are two ways that you get proteins improperly folded. The first is that this is how they are made. In bacteria that number is only ~10%, but in eukaryotes (i.e. Humans), that number can be as high as ~50%. These proteins need help from other proteins to fold correctly. The other way you get unfolded proteins is by stress. Usually it's either heat stress or oxidative stress that causes proteins to unfold (not surprisingly, the proteins which help other proteins fold are often called "heat-shock proteins").
As for wether or not "nature has solved this problem", well...of course it has. We're here right? I think the thing to remember is that evolution is not, strictly speaking, an optimization process. Rather, it is a "just good enough" process. For example, a dolphin has more efficient lungs than you, an eagle has better eyes than you, almost everything that walks the earth is faster and stronger than you, and you're actually rather poorly built for walking upright (a reason most of us will suffer lower back pain as we age), but none of that matters. For the niche that humans occupy, their large brains are sufficient to beat out all competitors, and yet chances are that some day something will come around with an even better brain and push us out.
The way this works with proteins is assuming that proteins fold to a conformation that is a global minimum. For any given combination of atoms, you would have to consider all possible conformations (which, as you point out, can more easily be expressed in terms of pair-wise and higher-order interactions). This is the classic NP-complete, traveling-salesman type problem. Now, not all proteins fold to a global energy minimum, but many or most do. So really, whether protein folding is P or NP depends on what you mean by the "protein folding problem".
If, by "protein folding problem", you mean determining the global energy minimum for any given chain of amino acids, then yes, this is NP. However, what Levinthal realized (with his paradox) was that if this was how proteins actually folded, it would take more than the age of the universe for a single protein to fold. This is even more paradoxical when you consider that most proteins fold on the millisecond to microsecond time scale. In other words, nature isn't solving an NP problem.
If, by "protein folding problem", you mean figuring out how a protein reaches its final conformation, then this is where the funnel comes in. Think of a protein on a surface in conformation space. Each spatial arrangement of atoms represents a different point in space. The surface represents the region of space that is accessible to the protein at a given energy. So, at high energy, the protein can wiggle around pretty much at will. All conformation space is open to it. However, as you lower the energy, fewer and fewer conformations are energetically allowed (that is, the protein no longer has enough energy to break certain hydrogen bonds or ionic interactions). Eventually, you lower the energy enough, and you find the global energy minimum.
Where this gets tricky is that there could be "traps" in the funnel; local energy minima that the protein can't escape from. If the protein gets caught in one of these traps, then it hasn't solved the NP problem of finding the global energy minimum. What's remarkable about proteins, however, is that the path they do follow (the one that's kinetically favorable) almost always avoids these traps. So, the protein is solving a P problem (finding the steepest path down the funnel), but in doing so also solves an NP problem (finding the global minimum).
If you think about it then, it's actually the funnel that has solved the NP problem (or rather, turned it into a P problem). This funnel is constructed by the laws of physics as they pertain to proteins, and it seems as though the unique properties of the 20 amino acids that make up proteins are the key to this NP to P conversion. Now, do I think this means that P = NP? No. The protein folding funnel is a heuristic, just like any other. Just because proteins usually find the global energy minimum, doesn't mean they always do. To absolutely, positively verify that they are at their global minimum, you still have to solve an NP hard problem.
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.
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.
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.
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.
That would imply that global minimums are not always used, and not always best.
Just like animals don't have internal combustion engines, there could be all kinds of interesting proteins that can't easily be reached by intermediary forms, and won't show up in nature.
The observation that nature seems to have solved an NP-complete problem is pure selection bias.
I'm not sure if I'd call it exactly selection bias. I guess it depends on what selection you're talking about. A really interesting aspect of NP-complete problems is that the can be solved in P, but require NP to check for correctness. To translate that to the world of proteins: proteins fold kinematically (P), but in doing so the reach thermodynamic minima (would take NP to verify that this is the case). In other words, while Nature might not have solved P=NP, it seems it has found a subset of molecules (the 20 amino acids) that allow it to "cheat".
Sorry, maybe I'm confused by what your saying, but thats not quite right.
NP Complete problems cannot be solved in polynomial time unless P = NP. But, given a potential solution, it can be verified in poly time.
I'll try to translate that to the world of proteins... but I don't know much biology.
Given a protein sequence, finding a folding that minimizes the energy (formally, finding a folding where the energy is less than some value K) cannot, in general, be done in polynomial unless P = NP. However, given a potential folding, we can verify if its the minimum (formally, we can verify if the energy is less than K).
Am I right with this? Can someone verify? I would hate to spread disinformation.
Let me try: A possible solution can be found in P time. But checking if it's THE solution (i.e. the best solution) requires NP time.
Does solve mean: solve a solution? or solve for the final (best) solution?
Does verify mean: verify that the solution works? or that you verified that it's the best answer?
P, NP, etc... are sets of yes/no or boolean problems. That is to say, the answer to these questions are always "Yes" or "No".
Lets take the traveling saleperson problem. You have a bunch of cities, and the distances between them. Also, your given a threshold, K. Your goal is to tell me if there is a path through the cities that has a distances less than K. All you output is "Yes" or "No"
This can be converted to an algorithm for finding the shortest path in polynomial time, which is the optimization version of the problem. But this problem is not in NP, its not even a candidate to be in NP.
However, I'm having trouble relating to what your saying. > A possible solution can be found in P time. But checking if it's THE solution (i.e. the best solution) requires NP time.
In terms of traveling salesperson, what is "a possible solution" and what is "the solution"? I'm guessing "the solution" is the shortest path, but if "a possible solution" means some path through all the cities... then that doesn't help much. Even for problems that are harder than NP, I can come up with a possible solution in polynomial time as long as the size of the solution is polynomial (I'm having difficulty thinking up an example at the moment).
Tell me if I'm being hard-headed or overly semantic...
So, yes, checking the solution is P. Finding the solution is NP. Optimizing for K is, therefore, intractable. Does that sound (at least somewhat) right?
One small thing though, its only intractable if P != NP.
http://www.scottaaronson.com/papers/npcomplete.pdf (also discusses other instances of nature seeming to solve NP-complete problems)
I know you're speaking loosely, but what is this supposed to mean? The folding is just a physical process, right? We may find it intractable to model or predict, but it still happens.
Very few known efficient algorithms for natural problems have exponents above 3 or 4. If P=NP would be proven, polynomial algorithms for NP-complete problems would likely to follow this "trend".
There is a lot of precedent in math to find existence proofs for results that are completely useless for finding a practical solution.
We'll have a Star Trek-like utopia once we are able to create human-like intelligence, and I think that's doable.
So, in that sense, if you can somehow reduce an NP-Complete problem to a problem in P, then yes, you would prove that P=NP. However, this would not be the only way to prove this. If you could just find a polynomial time algorithm for any NP-Complete problem, then you've proved P=NP.
Of course, most expert think P != NP, so if thats true then you'll fail in your attempts to do these...