I've always been intrigued by the P vs. NP problem. If I had to bet, I'd say P != NP, but imagining a world where P = NP is like imagining a world where a Star Trek-like utopia is suddenly achievable. It definitely would make the Internet feel like a "footnote" in history.
I have a feeling that if someone ever found that P=NP, it wouldn't be game-changing at all, but it would be like a proof that you can express the problem as O(x^2^2^2^2^10,000,000). (Or with the exponent being an even more absurdly large number, of which there are many.)
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".
Have you heard of Grahams number? (http://en.wikipedia.org/wiki/Graham%27s_number) It comes from a legitimate math proof, and it's unimaginably large. Or, I'm reminded of a proof, related to the Goldbach Conjecture, that every even number is the sum of at most 20 primes.
There is a lot of precedent in math to find existence proofs for results that are completely useless for finding a practical solution.
Slightly off topic, but I just wanted to point out that protein folding is not, strictly speaking, an NP problem. It can be expressed as one, but Levinthal's paradox essentially says that either the actual process of protein folding is not really NP or P=NP and nature has figured it out.
(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?)
Not that I have the biology chops to contribute to it myself, but a Protein Folding != NP debate is exactly the kind of discussion I'd like to see here.
Protein-folding can be expressed as a superset of molecular modeling(my area of research). In the strictest physical sense this is not a P problem if you consider the interactions of every atom with every other atom O(n!) for n atoms. No one does it that way of course. Once you ignore all but nearest neighbor interactions you have a problem that is polynomial time for n.
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 don't think a naive search would even be useful because finding globally minimal energy configurations isn't the goal. It's pretty unlikely that nature would happen to put such large systems as whole proteins in their lowest possible energy configurations when all that is really necessary is that they be stable (ie., locally minimal configurations). Especially if nature uses the tightly controlled folding process biohacker42 describes:
http://news.ycombinator.com/item?id=787731
It's true that proteins don't have to be in their global minima function, but they do if you want them to stick around for a long time and not cause problems (see: Creutzfeld-Jakob disease, Alzheimer's, Parkinson's, etc.). There was some research a while back that took the question of: what sort of molecule would have it's global minimum conformation also be the quickest to fold to? (Unfortunately, I don't have the citation handy...) The result they came up with was something that looked an awful lot like proteins.
I'm curious:
-- How long would they stay around for?
-- What sorts of problems? Would you need a lot of "bad" proteins to cause problems or just a few?
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/
They are also a fairly common thing to find in cells
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.
So, as I've alluded to elsewhere, 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. In other words, you can walk a traveling salesman to all the houses in the time it takes to walk to all the houses (that's a solution), but in order to verify that the path you walked was the shortest, you'd have walk all the possible paths (or at least, walk them until they were longer than the original path you walked, which is part of how heuristic methods of solving the problem work).
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.
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.
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.
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.
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.
Well then lets get the ball rolling. There's a theory that protein folding is like a funnel. That is to say, the initial probability space is huge, much like the wide end of a funnel.
But then it quickly collapses and the probability space becomes close enough to be computable by brute force.
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.
Hah, wow, thanks for the layman's description. That made sense!
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. ;)
Nature has found its way to some examples of folding that are kinematically accessible, and that are reachable through natural selection. This is a tiny part of the problem space.
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.
Ah, yes, nature doesn't have internal combustion engines, but all life is driven by super-efficient 3-step motors! (F_0F_1 ATPSynthase)
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".
> A really interesting aspect of NP-complete problems is that the can be solved in P, but require NP to check for correctness.
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.
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...
I think you're neither. My understanding is based on practical applications. That is, as far as I understand it, you're right about P and NP. From a practical point of view, the optimization of the problem depends on knowing what the smallest K is that has a "Yes" answer.
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?
http://en.wikipedia.org/wiki/Levinthals_paradox
pretty interesting, but it sounds more like the protein folding nature does isn't NP-complete. Like, Scott Aaronson says, nature may just have selected a subset of proteins that it happens to have figured out how to fold well:
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.
If we've solved protein folding we can fold cures for new viruses just as fast as jerks are folding new viruses. But in addition to that we can also fold proteins that will take care of old viruses and other diseases.
I don't think N = NP, because NP in polynomial time seems unnatural. Nature usually solves NP problems by natural selection, and from empiric observations it seems that finding the best answer is never a concern, usually a good enough one will do.
We'll have a Star Trek-like utopia once we are able to create human-like intelligence, and I think that's doable.
Frankly, I found that comment useful. The first question I had was if this was about a new solution, idea or a fresh development and the comment in question answers that in the negative. I suppose a lot of people here are already familiar with the problem, it's history and gct.
Here's something that I've always been confused about regarding P vs NP: It seems like what researchers are looking for is not necessarily an answer yes or no, but really a transform that would convert NP problems into P ones. I have a background in electrical engineering, where it is common to use Laplace and Fourier transforms to convert differential equations in the time domain to polynomial equations in the frequency domain, so I see the P vs NP issue to be somewhat analogous to that. Am I understanding the issue, or completely off?
Well, complexity theory does have this concept. I.e. you can convert one problem to another, they call it a reduction. I.e. you reduct problem A to problem B.
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...
Hah, I like how I tried to read the article from the NU wireless when I'm literally less than a building away from the guy but the ACM still required me to sign in.
http://blog.computationalcomplexity.org/
I am not in TCS, but I do enjoy what bits and pieces are understandable to me.