Vinay Deolalikar is the principal research scientist over at HP Labs and has recently claimed to have solved one of the most complex problems of Computer Science. The problem is actually so complex that Clay Mathematics Institute had announced a $1 Million prize award for whoever solves the problem. Whether Vinay would get the money or not will be decided once the institute can verify Vinay’s solution.
The problem that Vinay has tried to solve is called the P vs NP problem and deals with the existence of questions that can be answered quickly but require an impossibly long amount of time to be solved by any direct procedure. The complete details of the problem can be found here. As a result of his research, Vinay claims he has found proof that P is not equal to NP, meaning that an NP (nondeterministic polynomial time) problem can only be solved by brute force. The complete paper offered by Vinay can be accessed here.
Many scientists from around the world have expressed appreciation for Vinay’s effort but no body has started celebrating just yet. They all explained that Vinay’s proof and logic would have to be tested extensively before it can be claimed accurate.
Vinay has a Masters Degree in Electrical Engineering from IIT and a Ph.D in Electrical Engineering and Mathematics from University of Southern California. Vinay routinely gives lectures on Algebraic Geometry and Number Theory at Stanford University.