IITBian offers proof for P not equal to NP
IITB alum Dr. Vinay Deolalikar ('94) has offered a proof for the P=NP riddle. Dr. Deolalikar, who is with Hewlett-Packard Labs, has sent to peers copies of a proof he did stating that P is not equal to NP. Mathematicians are reviewing his work, a task that could go on for a long time. If he’s correct, Dr. Deolalikar will have figured out one of the Clay Mathematics Institute’s seven Millennium Prize Problems, for which they give $1 million prizes.
IIT Bombay alum Dr. Vinay Deolalikar ('94), a scientist at HP Labs in California, has proposed a proof for the famed P is not equalt to NP problem in mathematics.
Join the LinkedIn discussion on this development ... 
Step 1: Post Elusive 
Proof. Step 2: Watch Fireworks.
By John Markoff
The potential of Internet-based collaboration was vividly demonstrated this month when complexity theorists used blogs and wikis to pounce on a claimed proof for one of the most profound and difficult problems facing mathematicians and computer scientists.
Vinay Deolalikar, a mathematician and electrical engineer at Hewlett-Packard, posted a proposed proof of what is known as the “P versus NP” problem on a Web site, and quietly notified a number of the key researchers in a field of study that focuses on problems that are solvable only with the application of immense amounts of computing power. ... more.
From Discover Magazine's blog
P is not equal to NP. Seems simple enough. But if it’s true, it could be the answer to a problem computer scientists have wrestled for decades.
Vinay Deolalikar, who is with Hewlett-Packard Labs, has sent to peers copies of a proof he did stating that P is not equal to NP. Mathematicians are reviewing his work now—a task that could go on for a long time. If he’s correct, Deolalikar will have figured out one of the Clay Mathematics Institute’s seven Millennium Prize Problems, for which they give $1 million prizes.
What’s all the hubbub? First, an explainer:
The P versus NP question concerns the speed at which a computer can accomplish a task such as factorising a number. Some tasks can be completed reasonably quickly – in technical terms, the running time is proportional to a polynomial function of the input size – and these tasks are in class P. If the answer to a task can be checked quickly then it is in class NP.
That definition is pretty abstract, so here’s a more concrete example:
Clay imagines a college housing scenario wherein 400 students have applied for rooms at a college that can only accommodate 100 of them. A selection of 100 students must be paired together in rooms, but the dean of students has a list of pairings of certain students who cannot room together. The total possible number of pairings is ridiculously large — more than the total number of atoms in the universe — but the solutions, i.e. the list of pairings finally provided to the dean, is easy to check for errors: If one of the dean’s prohibited pairs is on the list, that’s an error.
Thus, if P were equal to NP, it would mean that problems that are easy to check—like this roommate match-up—must also be easy to solve. But if Deolalikar is correct and in fact P is not equal to NP, as many mathematicians already believed, then that ain’t necessarily so. And that would have practical meaning, according to Michael Sipser of MIT.
Deolalikar’s proof is now available to read online. New Scientist and Network World report that he pulled together tactics from different disciplines to show that an NP problem—whether a list of statements can be simultaneously correct or contradict one another—is not a P problem, because it can be easily checked but no computer can figure it out quickly from scratch.
In the days since the proof began to spread across the Internet, however, some math bloggers like Scott Aaronson have responded to the proof by saying yes, it’s lovely, but no, it probably isn’t going to stand.
... more.
Click here to follow all the stories on the web relating to this development ...
