The Status of the P Versus NP Problem

http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext

by yarapavan • 17 years ago

118 45 17 years ago

cacm.acm.org

brent• 17 years ago

For 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/

I am not in TCS, but I do enjoy what bits and pieces are understandable to me.

yarapavan• 17 years ago

Executive Summary: Still Open

asdlfj2sd33• 17 years ago

This is the top comment, really HN?

anshul• 17 years ago

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.

jdrock• 17 years 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• 17 years ago

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

jballanc10• 17 years 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?)

biohacker423• 17 years 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.

WilliamLP2• 17 years 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• 17 years 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".

bad_user• 17 years 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.

caryme• 17 years ago

Lance Fortnow is my academic adviser!

Locke1689• 17 years ago

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.

bhousel• 17 years ago

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?

roundsquare6• 17 years ago

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

The Status of the P Versus NP Problem

Related Stories