Processing .....please wait.. 
The article has been forwarded.... 
News >> General >>
P=NP riddle solved? Indian scientist proposes proof
By siliconindia
|
Wednesday, 11 August 2010, 22:48 IST
4.6 crore) for solving one of the seven Clay Mathematics Institute Millennium Problems, reports Samanth Subramanian of Mint.
In an email to his fellow researchers Deolalikar wrote that he had made several unsuccessful attempts trying other combinations of ideas before he began this work.
Before accepting by the mathematical community, the paper needs to be published in a major refereed journal. It has to be accepted by the mathematical community within two years of publication for Deolalikar to collect his Clay prize.
According to Stephen Cook, who has written the official description of the P=NP problem for the Clay Institute, Deolalikar has made a serious claim to have solved P vs NP.
The P=NP problem is a meta-problem with particular relevance to computer science. The 'P' in this equation refers to a class of problems; if the time needed to solve a problem does not grow exponentially with the data given, the problem is a type-P problem. An NP problem, on the other hand, is one for which you can check whether a proposed solution is really a solution in reasonable time.
The P=NP problem questions whether an NP problem is the same as a P problem. In other words, if a problem has solutions that can be verified in polynomial time, then can the problem also be solved in polynomial time?
Ever since the problem was stated, independently, by Cook and Leonid Levin in 1971, mathematicians have thought that P does not, in fact, equal NP - but no acceptable proof of that inequality has been found.
Deolalikar's proof, which seeks to establish that P is not equal to NP, has, in only a few days, churned up considerable excitement within the mathematical community.
Deolalikar's proof will be the second of the seven Millennium problems to have fallen within the last few years, if it is published and finds the 'general acceptance' that the Clay Institute requires.