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.
No comments:
Post a Comment