The Smart Techie was renamed Siliconindia India Edition starting Feb 2012 to continue the nearly two decade track record of excellence of our US edition.
September - 2010 - issue > In Focus
P=NP Riddle Solved? Indian Scientist Proposes Proof
si Team
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.
|
|
