6 ms·
The Status of the P Versus NP Problem
- brent 17y agoFor anyone who enjoyed reading this you may want to check out his (Lance Fortnow) blog (that he shares with Bill Gasarch). http://blog.computationalcomplexity.org/ http://blog.computationalcomplexity.org/ I am not in TCS, but I do enjoy what bits and pieces are understandable to me.
- yarapavan 17y agoExecutive Summary: Still Open
- asdlfj2sd33 17y agoThis is the top comment, really HN?
- anshul 17y agoFrankly, 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.
- jcl 17y agoOf course, the second sentence of the article also answers that question.
- jdrock 17y agoI'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 agoor we'd all just get wiped out by a super virus by some jerk messing around after solving protein folding.
- biohacker42 17y agoIf 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 agoSlightly 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 agoNot 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 agoI cannot agree more. Then it would get me off my butt and make me learn something about the topic, too.
- biohacker42 17y agoWell 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.
- caryme 17y agoLance Fortnow is my academic adviser!
- Locke1689 17y agoHah, 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.
- bhousel 17y agoHere'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?
- roundsquare 17y agoWell, 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...