P=NP Riddle Solved? Indian Scientist Proposes Proof Date:   Wednesday , September 01, 2010 Vinay Deolalikar, a scientist at Hewlett-Packard (HP) Labs in California has come up with a possible proof for the famed P=NP problem in mathematics. The feat can make him earn $1 million (Rs. 4.6 crore) for solving one of the seven Clay Mathematics Institute Millennium Problems. According to Stephen Cook, who has written the official description of the P=NP problem for the Clay Institute, ever since the problem was stated, mathematicians have thought that P does not, in fact, equal NP - but no acceptable proof of that inequality has been found. 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? Deolalikar’s proof seeks to establish that P is not equal to NP and if is published and finds the ‘general acceptance’ that the Clay Institute requires, it will be the second of the seven Millennium problems to have fallen within the last few years. 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