September - 2010 issue > In Focus

By si Team

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.

If you have more query about magazine please send mail to

Feb 12	Jan 12	Dec 11	Nov 11