Has the Devilish Math Problem "P vs NP" Finally Been Solved?

By Andrew Moseman | August 10, 2010 3:09 pm

VinayP is not equal to NP. Seems simple enough. But if it’s true, it could be the answer to a problem computer scientists have wrestled for decades.

Vinay Deolalikar, who is with Hewlett-Packard Labs, has sent to peers copies of a proof he did stating that P is not equal to NP. Mathematicians are reviewing his work now—a task that could go on for a long time. If he’s correct, Deolalikar will have figured out one of the Clay Mathematics Institute’s seven Millennium Prize Problems, for which they give $1 million prizes. (Grigory Perelman won one of the seven for solving the Poincaré conjecture, but turned down the money last month.)

What’s all the hubbub? First, an explainer:

The P versus NP question concerns the speed at which a computer can accomplish a task such as factorising a number. Some tasks can be completed reasonably quickly – in technical terms, the running time is proportional to a polynomial function of the input size – and these tasks are in class P. If the answer to a task can be checked quickly then it is in class NP [New Scientist].

That definition is pretty abstract, so here’s a more concrete example:

Clay imagines a college housing scenario wherein 400 students have applied for rooms at a college that can only accommodate 100 of them. A selection of 100 students must be paired together in rooms, but the dean of students has a list of pairings of certain students who cannot room together. The total possible number of pairings is ridiculously large — more than the total number of atoms in the universe — but the solutions, i.e. the list of pairings finally provided to the dean, is easy to check for errors: If one of the dean’s prohibited pairs is on the list, that’s an error [AOL News].

Thus, if P were equal to NP, it would mean that problems that are easy to check—like this roommate match-up—must also be easy to solve. But if Deolalikar is correct and in fact P is not equal to NP, as many mathematicians already believed, then that ain’t necessarily so. And that would have practical meaning, according to Michael Sipser of MIT.

Sipser … says that the P-versus-NP problem is important for deepening our understanding of computational complexity. “A major application is in the cryptography area,” Sipser says, where the security of cryptographic codes is often ensured by the complexity of a computational task. The RSA cryptographic scheme, which is commonly used for secure Internet transactions — and was invented at MIT — “is really an outgrowth of the study of the complexity of doing certain number-theoretic computations,” Sipser says [MIT News].

Deolalikar’s proof is now available to read online. New Scientist and Network World report that he pulled together tactics from different disciplines to show that an NP problem—whether a list of statements can be simultaneously correct or contradict one another—is not a P problem, because it can be easily checked but no computer can figure it out quickly from scratch.

In the days since the proof began to spread across the Internet, however, some math bloggers like Scott Aaronson have responded to the proof by saying yes, it’s lovely, but no, it probably isn’t going to stand.

Related Content:
80beats: Brilliant & Reclusive Russian Mathematician Doesn’t Need Your Prize Money
80beats: Can a Google Algorithm Predict Nobel Prize Winners?
DISCOVER Interview: The Math Behind the Physics Behind the Universe
DISCOVER: Top Math Stories of 2006, featuring Perelman’s achievement

Image: HP Labs

CATEGORIZED UNDER: Physics & Math, Technology
MORE ABOUT: computers, hacking, math
  • http://jetlib.com/news/ JetLib News

    Do you think he has solved it?

  • Brian Too

    Forget (P /= NP?).

    The problem I want solved is CB /= CWC. That is, Coffee Black is (Equal, Not Equal, Equivalent, or Approximately Equal) to Coffee With Cream.

  • qwuasi

    @Brian Too..yours is already proven.i tried it yesterday..so simple..i hope i get the 1million dollar offer.

  • John

    It probably has not been solved. A it seems a possible (very probable, IMO) flaw was found.

    http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof/

  • http://3-f-software.com atul kumthekar

    Good that he is in US of A, he could manage to attempt this and survive too ! :)

  • Viktor Ivanov

    I think that I have solved that problem long ago (see P-versus-NP page), and I have submitted my respective papers to certain central computer sciense journals. However, my papers were rejected without indecation of any concrete substantial flaws.

  • Ravindra Chourase

    Solution of P versus NP problem

    Kindly have a look inside…..here is the link:
    http://solutionpversusnp.blogspot.com/

  • Ravindra Chourase

    Dear Sir,

    Here are some of the main points about the proof:

    1) NP-intermediate problems do not exist as the problems believed to
    of this kind are NP-Complete.
    for example the integer factorization problem is NP-Complete, so the
    polynomial time hierarchy will collapse to its first level (i.e., NP
    will equal co-NP).

    Since P = NP if and only if P = PH.
    (As the former we have established that NP = co-NP, which in turn
    implies that NP = PH)

    Existing proof techniques are not powerful enough to answer the
    question, So here I am going to introduce a new concept of Relativity
    in Computational Complexity.

    So, while considering the above result now lets consider the case of
    controlled relativity:

    1) P = PH; which implies

    2) P= NP

    And in the case of uncontrolled relativity:

    1) P!= HP; which implies

    2) P!= NP

    Explanation of the assumption made by Scott Aaronson, MIT regarding P= NP.

    For details please have a look at my blog
    http://solutionpversusnp.blogspot.com/ , where I have explained the
    concept of relativity in detail with the help of Rubik Cube.

    Thank you

    Ravindra Chourase
    Indian Institute of Technology Kharagpur

  • http://www.frozenyogurtrecipe.org/frozenyogurtarticles/ FrozenYogurtRecipe

    Thanks for the post. I am currently working on my frozen yogurt site at: http://www.frozenyogurtrecipe.org/frozenyogurtarticles/. In fact I got some great design tips from Has the Devilish Math Problem “P vs NP” Finally Been Solved? | 80beats | Discover Magazine. Looking forward to reading more.

NEW ON DISCOVER
OPEN
CITIZEN SCIENCE
ADVERTISEMENT

Discover's Newsletter

Sign up to get the latest science news delivered weekly right to your inbox!

80beats

80beats is DISCOVER's news aggregator, weaving together the choicest tidbits from the best articles covering the day's most compelling topics.
ADVERTISEMENT

See More

ADVERTISEMENT
Collapse bottom bar
+

Login to your Account

X
E-mail address:
Password:
Remember me
Forgot your password?
No problem. Click here to have it e-mailed to you.

Not Registered Yet?

Register now for FREE. Registration only takes a few minutes to complete. Register now »