Communications of the ACM
The Status of the P Versus NP Problem
Illustration by C.E.B. Reas
It's one of the fundamental mathematical problems of our time, and its importance grows with the rise of powerful computers.
The full text of this article is premium content
Comments
Jinsei Yamaguchi
I have already solved this problem. The final answer is "P vs NP problem vanishes". For the definition of "vanish" and the proof, see my Japanese site http://www.int2.info/news1.htm
Moshe Vardi
Not reading Japanese, it is hard for me even to understand what the claim is. I'd suggest to Jinsei Yamaguchi to submit his result to a scholarly publication for review.
Michael Wojcik
I'd like to congratulate Dr Fortnow and the CACM editors for one of the best pieces I've read in CACM in years. This article is engaging and clear, on a topic of broad theoretical and practical interest.
Andras Olah
A problem is just only a matter of debate.
The only thing we can not control is the time.
Assuming that a problem when you dissolve it, its importance is relative, because what can already solve a minor. The problem is the importance of the correct definition of the most important and hence the explanatory memorandum in relation to the proper time.
If a calculation is needed done today, but only months later, I get accurate results. It is no longer important to the results tomorrow. Unless my life depends on it, because it certainly calculated! :)
There are no insoluble problems! You do not always worth the time to devote as much.
Anonymous
Solution of P versus NP problem.
Here is the link......kindly have a look:
http://solutionpversusnp.blogspot.com/
Anonymous
"P=NP" doesn't imply "public-key cryptography becomes impossible". Nor does it imply "short, fully logical proofs". This is because the order for polynomial time algorithms can still be astronomical.
Search, for example, for "inefficient" at http://portal.acm.org/citation.cfm?id=803896
("Linear time algorithm for isomorphism of planar graphs", by Hopcroft / Wong)
I don't think that is a good point to make.
Stephan
Anonymous
Thank you for an excellent article! (And, if I am correctly using a cultural term from a generation younger than mine "respect" for the "New Hope" reference.)
My own intuition is, that P <> NP, but I would love to be proved wrong.
One line, however, struck me.
> Nevertheless, Mulmuley believes it will take about 100 years to
> carry out this program, if it works at all.
This is the piece in which I have a strong disagreement. I believe that the calculation of "about 100 years" fails to adequately take into account the advances in machine-based theorem proving.
At the risk of sounding "singularitian", I would be willing to wager that the problem will:
EITHER be solved by 2050
OR prove unsolveable, and not be solved by 2500
P Albert
To the two posters who provided solutions to the P vs NP problem, you solved a different P vs NP problem than the one that everyone else is discussing. :) Good work, though!
Anonymous
The real issue of P vs NP is it's framed incorrectly. If one thinks of the costs in terms of physics I imagine many problems would disappear. This is the problem when being caught up in the mathematics without a sound understanding of the physics of the world itself. You've framed the problem incorrectly to begin with so you end up pursuing stupid questions.
Anonymous
This has been very breadth-full coverage of the topic.Thanks to the editors for the same