Vinay Deolalikar Indian computer scientist and researcher Country: India

1. Biography of Vinay Deolalikar
2. Introduction to his Manuscript
3. The P versus NP Problem
4. Reaction to the Manuscript

Biography of Vinay Deolalikar

Vinay Deolalikar is an Indian computer scientist and researcher currently working at HP Labs. He was born in New Delhi, India. He obtained his Master's degree in Electrical Engineering from the Indian Institute of Technology in Bombay. Later, he earned a Ph.D. degree in Philosophy from the University of Southern California.

Introduction to his Manuscript

On August 6, 2010, Vinay sent a manuscript to leading researchers worldwide containing his variation of a solution to one of the "Millennium Prize Problems" - the P versus NP problem. The "Millennium Prize Problems" are seven problems at the intersection of mathematics and other fields. The Clay Mathematics Institute has promised a $1 million prize for solving each of these problems. So far, only one of the seven problems has been officially solved by Russian mathematician Grigori Perelman, who proved the Poincaré conjecture.

The P versus NP Problem

The equality of the P and NP classes is one of the oldest problems in computer science and algorithm theory. The class NP includes a set of problems that can be solved trivially, but the solution time grows exponentially with the input size. It is believed that there might be an algorithm that allows solving these problems in a "polynomial time," but no one has been able to prove or disprove this fact. Practical investigations suggest that the P and NP classes are likely not equal. If someone can prove otherwise, it would be a monumental breakthrough in computer science. Many NP class problems could be solved in reasonable time, and cryptography would be greatly affected as most information security systems rely on the assumption that decrypting modern codes is computationally difficult within the NP class.

Reaction to the Manuscript

The news about Vinay's manuscript was first reported in a blog post by Greg Baker, spreading quickly across the internet. At present, there are both supporters and opponents of Vinay's proof. Scott Aaronson, for example, has personally pledged an additional $200,000 to the promised $1 million from the Clay Institute if the solution turns out to be correct. Global analysts are yet to thoroughly analyze Deolalikar's work, which consists of 116 pages, and draw conclusions about the correctness of the proof.