# The Status of the P Versus NP Problem

By Lance Fortnow

Communications of the ACM, Vol. 52 No. 9, Pages 78-86
10.1145/1562164.1562186

It's one of the fundamental mathematical problems of our time, and its importance grows with the rise of powerful computers.

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

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