Sign In

Communications of the ACM

Review article

The Status of the P Versus NP Problem


View as: Print Mobile App ACM Digital Library In the Digital Edition Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook
stylized network graph

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


View More Comments

Log in to Read the Full Article

Sign In

Sign in using your ACM Web Account username and password to access premium content if you are an ACM member, Communications subscriber or Digital Library subscriber.

Need Access?

Please select one of the options below for access to premium content and features.

Create a Web Account

If you are already an ACM member, Communications subscriber, or Digital Library subscriber, please set up a web account to access premium content on this site.

Join the ACM

Become a member to take full advantage of ACM's outstanding computing information resources, networking opportunities, and other benefits.
  

Subscribe to Communications of the ACM Magazine

Get full access to 50+ years of CACM content and receive the print version of the magazine monthly.

Purchase the Article

Non-members can purchase this article or a copy of the magazine in which it appears.