View Feed
group-icon
Coffee Room
Discuss anything here - everything that you wish to discuss with fellow engineers.
12940 Members
Join this group to post and comment.
Kaustubh Katdare
Kaustubh Katdare • Aug 12, 2010

Has Vinay Deolalikar Solved The P Versus NP Problem [Finally]?

One of the most difficult unsolved mathematical problem in Computer Science has been cracked [or at least, Mr. Vinay Deolikar of HP Research Arm claims so].

Wikipedia Quotes -

In essence, the question P = NP? asks:
Suppose that yes answers to a yes or no question can be verified quickly. Then, can the answers themselves also be computed quickly?
The theoretical notion of quick used here is that of an algorithm that runs in polynomial time. The general class of questions for which some algorithm can provide a yes-or-no answer in polynomial time is called "class P" or just "P".




Taken from :-https://expressbuzz.com/world/indian-cracks-worlds-toughest-maths-problem/197316.html

LONDON: An Indian-origin computer scientist based in the US claims to have solved one of the world's most complex mathematical riddles.Vinay Deolalikar, who works with the US multinational information technology corporation Hewlett-Packard in California, believes he has solved the problem of "P versus NP", Daily Telegraph reported Wednesday.The Massachusetts-based Clay Mathematical Institute has categorised "P vs NP" as one of the seven millennium problems. It is considered the "most difficult" one to be solved.If his claim is proved correct, Deolalikar stands to earn a $1 million prize.Many maths calculations involve checking a large number of possible solutions and that could be beyond the current capability of any computer. P vs NP looks at the possibility of whether there is a way of arriving at the answers to the calculations faster in the first place.Deolalikar's paper that was posted online Friday claims that P, which refers to problems whose solutions are easy to find and verify, is not the same as NP, which refers to problems whose solutions are almost impossible to find but easy to verify, the report said.Scott Aaronson, associate professor of computer science at the Massachusetts Institute of Technology, wasn't too impressed and vowed to pay Deolalikar an additional $200,000 if the solution was accepted by Clay Institute.He wrote in his blog: "If P?NP has indeed been proved, my life will change so dramatically that having to pay $200,000 will be the least of it."Mathematicians Stephen Cook and Leonid Levin formalised the problem in 1971.

Share this content on your social channels -