5 ms·

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

by jdrock 17y ago

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.

nazgulnarsil 17y ago
or we'd all just get wiped out by a super virus by some jerk messing around after solving protein folding.
- biohacker42 17y ago
  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.
- jballanc 17y ago
  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?)
  - calambrac 17y ago
    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.
    - PieSquared 17y ago
      I cannot agree more. Then it would get me off my butt and make me learn something about the topic, too.
      - biohacker42 17y ago
        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.
        PieSquared 17y ago
        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. ;)
    - quantumhobbit 17y ago
      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'd love to hear from someone who knows more.
      - adrianbg 17y ago
        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 http://news.ycombinator.com/item?id=787731
        jballanc 17y ago
        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.
        17y ago
  - idlewords 17y ago
    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.
    - jballanc 17y ago
      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".
      - roundsquare 17y ago
        > 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.
        ars 17y ago
  - adrianbg 17y ago
    http://en.wikipedia.org/wiki/Levinthals_paradox 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: http://www.scottaaronson.com/papers/npcomplete.pdf http://www.scottaaronson.com/papers/npcomplete.pdf (also discusses other instances of nature seeming to solve NP-complete problems)
  - bmm6o 17y ago
    > or P=NP and nature has figured it out. 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.
WilliamLP 17y ago
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.)
- smikhanov 17y ago
  Very unlikely. 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".
  - WilliamLP 17y ago
    Have you heard of Grahams number? (http://en.wikipedia.org/wiki/Graham%27s_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.
bad_user 17y ago
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.

by jdrock 17y ago

nazgulnarsil 17y ago

or we'd all just get wiped out by a super virus by some jerk messing around after solving protein folding.

biohacker42 17y ago
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.
jballanc 17y ago
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?)
- calambrac 17y ago
  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.
  - PieSquared 17y ago
    I cannot agree more. Then it would get me off my butt and make me learn something about the topic, too.
    - biohacker42 17y ago
      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.
      - PieSquared 17y ago
        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. ;)
  - quantumhobbit 17y ago
    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'd love to hear from someone who knows more.
    - adrianbg 17y ago
      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 http://news.ycombinator.com/item?id=787731
      - jballanc 17y ago
        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.
        17y ago
- idlewords 17y ago
  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.
  - jballanc 17y ago
    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".
    - roundsquare 17y ago
      > 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.
      - ars 17y ago
- adrianbg 17y ago
  http://en.wikipedia.org/wiki/Levinthals_paradox 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: http://www.scottaaronson.com/papers/npcomplete.pdf http://www.scottaaronson.com/papers/npcomplete.pdf (also discusses other instances of nature seeming to solve NP-complete problems)
- bmm6o 17y ago
  > or P=NP and nature has figured it out. 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.

WilliamLP 17y ago

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.)

smikhanov 17y ago
Very unlikely. 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".
- WilliamLP 17y ago
  Have you heard of Grahams number? (http://en.wikipedia.org/wiki/Graham%27s_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.

bad_user 17y ago

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.