Channels ▼

Mark Nelson

Dr. Dobb's Bloggers

P ≠ NP?

August 10, 2010

You may have never heard of Vinay Deolalikar, but there is a chance that he may become next year's Turing Award winner, not to mention an overnight millionaire. It seems that Vinay dropped the news at the start of this week that he had proven that P does not equal NP. In short, this proof means that many problems we suspect are hard to solve are in fact provably hard to solve. Whether his proof succeeds or not, the Interwebs are abuzz with the news.

P versus NP is arguably the biggest unanswered problem in Computer Science, and proving it one way or another will cascade into new results and conclusions in many areas of computing and mathematics. The problem is at least 40 years old, and despite people literally devoting their entire careers to the problem, has yet to be decided. Some researchers suspect it can't be proved, although this has not been proven either.

When a famous problem like this has been stewing for so long, it is not unusual to see sporadic cries of proof, but these need to be taken with a grain of salt. The first test is to see if the person is a flake with a proof that won't survive a casual scan. Passing that test, the proof then has to endure the normal peer review process. Proofs that plumb difficult new ground can take years to be accepted.

It appears that Deolalikar has passed the first test - people are seriously studying his proof. However, given its complexity and length, you can expect that general acceptance will not happen overnight. More likely, specific problems will arise, challenges will be published, and Deolalikar will either respond, modify his proof, or retreat for more study. If he indeed has the golden ticket, he will be cashing a million dollar prize from the Clay Mathematics Institute sometime soon.

It's remarkable news indeed, and perhaps the only way it would have been more remarkable would have been with a proof that P equals NP.

Feel like weighing in? Check out the proof yourself and see what you think.

Related Reading

More Insights

Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.